Cod sursa(job #914253)

Utilizator smaraldaSmaranda Dinu smaralda Data 13 martie 2013 23:43:16
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<stdio.h>
#include<math.h>
#include<algorithm>
#define eps 1.e-6
using namespace std;
struct POINT { double x,y; };
POINT p[1010];
int n;
bool cmp(POINT a, POINT b)
{
    if(fabs(a.x-b.x)<eps)
        return a.y<b.y;
    return a.x<b.x;
}

bool check (POINT uno, POINT dos)
{
    if(fabs(uno.x-dos.x)<eps)
        return uno.y<dos.y;
    return uno.x<dos.x;

}

bool bs(POINT caut)
{
    int st,dr,med;
    st=1; dr=n;
    while(st<=dr)
        {
            med=(st+dr)/2;
            if(fabs(p[med].x-caut.x)<=eps && fabs(p[med].y-caut.y)<=eps)
                return 1;
            if(check(caut,p[med]))
                dr=med-1;
            else
                st=med+1;
        }
    return 0;
}

int main()
{
    freopen("patrate3.in","r",stdin);
    freopen("patrate3.out","w",stdout);
    int i,j,res=0;
    double t1,t2;
    POINT A,B;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        {
            scanf("%lf%lf",&t1,&t2);
            p[i].x=t1; p[i].y=t2;
        }

    sort(p+1,p+1+n,cmp);

    for(i=1;i<=n;i++)
        for(j=i+1;j<=n ;j++)
            {
                A.x=p[i].x+p[i].y-p[j].y;
                A.y=p[i].y+p[j].x-p[i].x;
                B.x=p[i].y+p[j].x-p[j].y;
                B.y=p[j].x+p[j].y-p[i].x;
                if(bs(A) && bs(B))
                    res++;
            }
    printf("%d\n",res/2);
    return 0;
}