Cod sursa(job #681346)
Utilizator | Data | 16 februarie 2012 22:34:48 | |
---|---|---|---|
Problema | Patrate 3 | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 3.59 kb |
#include<cstdio>
#include<cmath>
#include<algorithm>
typedef struct { int x,y; }punct;
punct a[1004];
const int inm=10000;
bool compare(punct b,punct a){ if(a.x>b.x)return 1; else if(a.x==b.x && a.y>b.y)return 1; else return 0; }
int main(void){
freopen ("patrate3.in","r",stdin);
freopen ("patrate3.out","w",stdout);
int i,n,v,u,x2,y2,x3,y3,dx,dy,mx,my,i1,j1,mij,j,nr=0;
scanf("%d\n",&n);
for(i=1;i<=n;++i){
scanf("%d.%d",&v,&u);
if(v<0)a[i].x=(v*inm)-u;
else a[i].x=(v*inm)+u;
scanf(" %d.%d\n",&v,&u);
if(v<0)a[i].y=(v*inm)-u;
else a[i].y=(v*inm)+u;
}
std::sort(a+1,a+n+1,compare);
for(i=1;i<=n;++i)
for(j=i+1;j<=n;++j)
if(a[i].y<a[j].y){
mx=(a[i].x+a[j].x)/2;
my=(a[i].y+a[j].y)/2;
dx=abs(mx-a[i].x);
dy=abs(my-a[i].y);
x2=mx+dy; y2=my-dx;
x3=mx-dy; y3=my+dx;
i1=1; j1=n;
while(j1-i1>1){
mij=i1+(j1-i1)/2;
if(a[mij].x<x2)i1=mij;
else j1=mij;
}
if(j1<=n)
if(a[j1].x==x2 && a[j1].y==y2){
i1=1; j1=n;
while(j1-i1>1){
mij=i1+(j1-i1)/2;
if(a[mij].x<x3)i1=mij;
else j1=mij;
}
if(a[j1].x==x3 && a[j1].y==y3)++nr;
}
}
else
{
mx=(a[i].x+a[j].x)/2;
my=(a[i].y+a[j].y)/2;
dx=abs(mx-a[i].x);
dy=abs(my-a[i].y);
x2=mx-dy; y2=my-dx;
x3=mx+dy; y3=my+dx;
while(j1-i1>1){
mij=i1+(j1-i1)/2;
if(a[mij].x<x2)i1=mij;
else j1=mij;
}
if(j1<=n)
if(a[j1].x==x2 && a[j1].y==y2){
i1=1; j1=n;
while(j1-i1>1){
mij=i1+(j1-i1)/2;
if(a[mij].x<x3)i1=mij;
else j1=mij;
}
if(a[j1].x==x3 && a[j1].y==y3)++nr;
}
}
printf("%d",nr);
//for(i=1;i<=n;++i)printf("%d %d\n",a[i].x,a[i].y);
return 0;
}