Cod sursa(job #1487729)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 17 septembrie 2015 13:10:08
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 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(y[i]<y[j]) {
            for(o=0,t=k;t;t>>=1)
            if(o+t<=n&&((!C(x[o+t],u+dy)&&x[o+t]<u+dy)||(C(x[o+t],u+dy)&&(C(y[o+t],v-dx)||y[o+t]<v-dx))))
                o+=t;
            if(C(x[o],u+dy)&&C(y[o],v-dx)) {
                for(l=0,t=k;t;t>>=1)
                if(l+t<=n&&((!C(x[l+t],u-dy)&&x[l+t]<u-dy)||(C(x[l+t],u-dy)&&(C(y[l+t],v+dx)||y[l+t]<v+dx))))
                    l+=t;
                if(C(x[l],u-dy)&&C(y[l],v+dx))
                    r++;
            }
        }
    }
    printf("%d",r);
}