# 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.