Cod sursa(job #2774939)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 13 septembrie 2021 17:09:49
Problema Patrate 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include<cstdio>
#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,x,y,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,x=abs(u-a[i].x),y=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+y)&&a[o+t].x<u+y)||(C(a[o+t].x,u+y)&&(C(a[o+t].y,v-x)||a[o+t].y<v-x))))
                        o+=t;
                if(C(a[o].x,u+y)&&C(a[o].y,v-x)) {
                    for(l=0,t=k;t;t>>=1)
                        if(l+t<=n&&((!C(a[l+t].x,u-y)&&a[l+t].x<u-y)||(C(a[l+t].x,u-y)&&(C(a[l+t].y,v+x)||a[l+t].y<v+x))))
                            l+=t;
                if(C(a[l].x,u-y)&&C(a[l].y,v+x))
                    ++r;
            }
        }
    }
    printf("%d",r);
    return 0;
}