p1971.cpp

大概POJ上50道比较难的题的代码

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 1010;
struct point{ int x,y; };
struct seg{ point a; int s,t; };
bool cmp(seg a,seg b){ return a.a.x < b.a.x || a.a.x == b.a.x && a.a.y < b.a.y; }
bool ok(seg a,seg b){
    return a.s != b.s && a.s != b.t && a.t != b.s && a.t != b.t; 
}
point a[MAXN];
seg f[MAXN*MAXN];
int main(){
    freopen("t.txt","r",stdin);
    freopen("r.txt","w",stdout);
    int N;
    cin >> N;
    while(N--){
        int nf(0);
        seg temp;
        int n;
        cin >> n;
        for(int i = 0;i < n;++i) scanf("%d%d",&a[i].x,&a[i].y);
        for(int i = 0;i < n;++i)
            for(int j = i+1;j < n;++j){
                f[nf].a.x = a[i].x - a[j].x;
                f[nf].a.y = a[i].y - a[j].y;
                if(f[nf].a.x < 0){
                    f[nf].a.x = -f[nf].a.x;
                    f[nf].a.y = -f[nf].a.y;
                }
				if(f[nf].a.x == 0) f[nf].a.y = abs(f[nf].a.y);
                f[nf].s = i; f[nf].t = j;
                ++nf;
            }
        sort(f,f+nf,cmp);
//        for(int i = 0;i < nf;++i) cout << f[i].a.x << " " << f[i].a.y << " " << f[i].s << " " << f[i].t << endl;
        int ans(0);
        for(int i = 0;i < nf;++i)
            for(int j = i+1;j < nf && f[i].a.x == f[j].a.x && f[i].a.y == f[j].a.y;++j)
                if(ok(f[i],f[j])) ++ans;
        cout << ans/2 << endl;
    }
}