Cod sursa(job #1487732)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 17 septembrie 2015 13:13:27
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
struct P { int x,y; };
P a[1001];
int n,i,r,k,j,t,l,u,v,dx,dy,o;
double c[1001],d[1001];
int C(int a,int b) { return abs(b-a)<=10; }
int D(P a,P b) { return (!C(a.x,b.x)&&a.x<b.x)||(C(a.x,b.x)&&a.y<b.y); }
int main() {
    freopen("patrate3.in","r",stdin),freopen("patrate3.out","w",stdout),scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%lf%lf",&c[i],&d[i]),a[i].x=(int)ceil(100000*c[i])-(int)(ceil(100000*c[i]))%2,a[i].y=(int)ceil(100000*d[i])-(int)(ceil(100000*d[i]))%2;
    sort(a+1,a+n+1,D);
    for(k=1;k<=n;k<<=1);
    for(i=1;i<n;i++)
    for(j=i+1;j<=n;j++) {
        u=(a[i].x+a[j].x)/2,v=(a[i].y+a[j].y)/2,dx=abs(u-a[i].x),dy=abs(v-a[i].y);
        if(a[i].y<a[j].y) {
            for(o=0,t=k;t;t>>=1)
            if(o+t<=n&&((!C(a[o+t].x,u+dy)&&a[o+t].x<u+dy)||(C(a[o+t].x,u+dy)&&(C(a[o+t].y,v-dx)||a[o+t].y<v-dx))))
                o+=t;
            if(C(a[o].x,u+dy)&&C(a[o].y,v-dx)) {
                for(l=0,t=k;t;t>>=1)
                if(l+t<=n&&((!C(a[l+t].x,u-dy)&&a[l+t].x<u-dy)||(C(a[l+t].x,u-dy)&&(C(a[l+t].y,v+dx)||a[l+t].y<v+dx))))
                    l+=t;
                if(C(a[l].x,u-dy)&&C(a[l].y,v+dx))
                    r++;
            }
        }
    }
    printf("%d",r);
}