Cod sursa(job #1765002)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 26 septembrie 2016 10:22:41
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda cerculdeinfo-lectia1-hashuri.rabinkarp Marime 1.28 kb
#include <cstdio>
#include <algorithm>
#define x first
#define y second
#define var 0.00001
using namespace std;
 
int N,Sol;
double DX,DY;
pair <double,double>v[1001],mij,P1,P2;
bool BS(double x,double y)
{
    int lw=1,mid,hi=N;
    while(lw<=hi)
    {
        mid=(hi+lw)>>1;
        if(abs(x-v[mid].x)<=var&&abs(y-v[mid].y)<=var)
            return true;
 
        if((abs(x-v[mid].x)>=var&&x>v[mid].x)||(abs(x-v[mid].x)<=var&&(abs(y-v[mid].y)>=var&&y>v[mid].y)))
            lw=mid+1;
        else hi=mid-1;
    }
    return false;
}
int main()
{
    freopen("patrate3.in","r",stdin);
    freopen("patrate3.out","w",stdout);
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        scanf("%lf %lf",&v[i].x,&v[i].y);
    sort(v+1,v+1+N);
    for(int i=1;i<=N;i++)
        for(int j=i+1;j<=N;j++)
        {
            mij.x=(v[i].x+v[j].x)/2;
            mij.y=(v[i].y+v[j].y)/2;
            DX=abs(mij.x-v[i].x);
            DY=abs(mij.y-v[i].y);
            if(v[i].y<v[j].y)
                P1.x=mij.x+DY,P1.y=mij.y-DX,P2.x=mij.x-DY,P2.y=mij.y+DX;
            else
                P1.x=mij.x-DY,P1.y=mij.y-DX,P2.x=mij.x+DY,P2.y=mij.y+DX;
            if(BS(P1.x,P1.y)&&BS(P2.x,P2.y))
                Sol++;
        }
    printf("%d",Sol/2);
    return 0;
}