20200321(ABC)题解 by 马鸿儒 孙晨曦

 昨天A就是暴力,然后注意一下特判,
B就是先排序,然后n^2一个一个试试就行了
 
马鸿儒
 
 C题题解:应该不难想到答案是相同横坐标的点对数+相同纵坐标的点对数-相同坐标的点对数(减去的是重复算的一遍)
所以统计每个横坐标上的点数cntx[i]、每个纵坐标上的点数cnty[j]、每个点上的点数cntxy[k],
答案为cntx[i]*(cntx[i]-1)/2 + cnty[j]*(cnty[j]-1)/2 - cntxy[k]*(cntxy[k]-1)/2;
(i枚举每个横坐标,j枚举每个纵坐标,k枚举每个点)
n是2e5,坐标是1e9,所以要用三个map统计,存坐标点的map用pair(或者重载<的struct,或者map套map)。代码:
 
孙晨曦
 
原文地址:https://www.cnblogs.com/QLU-ACM/p/12544404.html