Poj Solution 2002

http://poj.org/problem?id=2002

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define DIFF 20000
#define MAX 1005
#define NUM 40005
#define EP 1e-8
#define LIM 1e-6
#define PI acos(-1.0)
struct pt{
    int x,y;
};
pt p[MAX];
int s[NUM],e[NUM];
int n;
int Max,Min;
bool cmp(pt a,pt b)
{
    return a.x<b.x || a.x==b.x && a.y<b.y;
}

void input()
{
    int i;
    Min=NUM,Max=-1;
    for (i=0;i<n;i++) {
        scanf("%d %d",&p[i].x,&p[i].y);
        p[i].x+=DIFF;
        if (p[i].x<Min) Min=p[i].x;
        if (p[i].x>Max) Max=p[i].x;
    }
    std::sort(p,p+n,cmp);
    for (i=1;i<n;i++)
    memset(s+Min,-1,(Max-Min+2)*sizeof(int));
    s[p[0].x]=0;
    for (i=1;i<n;i++) {
        if (p[i].x!=p[i-1].x) {
            e[p[i-1].x]=i-1;
            s[p[i].x]=i;
        }
    }
    e[p[n-1].x]=n-1;
}

int search(pt z)
{
    if (z.x<Min || z.x>Max || s[z.x]<0) return 0;    
    int a=s[z.x], b=e[z.x], mid,x=z.x,y=z.y;
    while (a<b) {
        mid=(a+b)>>1;
        if (p[mid].y==y) {a=mid; break;}
        else if (p[mid].y<y) a=mid+1;
        else b=mid;
    }
    return (p[a].x==z.x && p[a].y==z.y);
}

void solve()
{
    int i,j;
    double alpha,d;
    double ax,ay,bx,by;
    pt a,b;
    int ans=0;
    for (i=0;i<n;i++) {
        for (j=i+1;j<n;j++) {
            if (p[j].x==p[i].x)    {
                a.x=p[i].x+p[j].y-p[i].y;
                a.y=p[j].y;
                b.x=p[i].x+p[j].y-p[i].y;
                b.y=p[i].y;
                if (search(a) && search(b)) ++ans;
            }
            else if (p[j].y>p[i].y) {

                a.x=p[j].y-p[i].y+p[j].x; a.y=p[i].x-p[j].x+p[j].y;
                if (!search(a)) continue;

                b.x=(p[i].x+a.x)-p[j].x; b.y=(p[i].y+a.y)-p[j].y;
                if (search(b)) ++ans;
            }
        }
    }
    printf("%dn",ans);
}

int main()
{
    while (scanf("%d",&n)==1) {
        if (!n) break;
        input();
        solve();
    }    
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *