给出n个点。问选出4个点作为定点,能够组成多少个平行与坐标轴的矩形。
点按照x排序
n^2挑选出 垂直x轴的线段,按照y1排序
#include<iostream> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N=1e5 ; struct T{ int x,y; bool operator<(T &rh){ if(x==rh.x) return y<rh.y; return x<rh.x; } }a[N]; struct Q{ int y1,y2; Q(int y1,int y2):y1(y1),y2(y2){} bool operator<(Q &rh){ if(y1==rh.y1) return y2<rh.y2; return y1<rh.y1; } }; int n; int C2(int x){ return x*(x-1)/2; } void sov(int cas){ vector<Q> vec; int i,j,x,y; cin>>n; for(i=1;i<=n;i++) cin>>a[i].x>>a[i].y; sort(a+1,a+1+n) ; for(i=1;i<=n;i++) for(j=i+1;j<=n;j++){ if(a[i].x-a[j].x) break; vec.push_back(Q(a[i].y,a[j].y)); } sort(vec.begin(),vec.end()); int ans=0,cnt=1; for(i=0;i<vec.size();i++){ if(vec[i].y1==vec[i-1].y1&& vec[i].y2==vec[i-1].y2) cnt++; else ans+= C2(cnt), cnt=1; } ans+=C2(cnt) ; printf("Case %d: %d\n", cas, ans); } signed main(){ int tes,cas=0; cin>>tes; while(tes--) sov(++cas); }
标签:include,个点,int,tes,10574,UVA,Counting From: https://www.cnblogs.com/towboa/p/17342151.html