Cod sursa(job #1073650)

Utilizator lianaliana tucar liana Data 6 ianuarie 2014 17:42:03
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.7 kb
//100
#include<stdio.h>
#include<algorithm>
#include<cmath>
using namespace std;
#define nmax 1005
#define eps 0.00001
struct punct{double x, y;};
long n, i, st, dr, mij, rez, j, p, k, q;
punct v[nmax], a, b, c;
bool ok, ex[nmax][nmax];

void citire()
{
    scanf("%ld",&n);
    for (i=1;i<=n;i++)
        scanf("%lf %lf",&v[i].x,&v[i].y);
}

bool cmp(punct a, punct b)
{
    if (fabs(a.x-b.x)>eps)
        return (a.x<b.x);
    return (a.y<b.y);
}

bool eg(punct a, punct b)
{    return  ((fabs(a.x-b.x)<=eps)&&(fabs(a.y-b.y)<=eps));}

void cauta()
{
    st=1;  dr=n;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (cmp(v[mij],c))
            st=mij+1;
        else
            dr=mij-1;
    }
    p=0;
    if ((st-1>=1)&&(eg(v[st-1],c)))
        p=st-1;
    if (eg(v[st],c))
        p=st;
    if ((st+1<=n)&&(eg(v[st+1],c)))
        p=st+1;

}

void rezolvare()
{
    for (i=1;i<=n;i++)
        for (j=i+1;j<=n;j++)
            if ((!ex[i][j])&&(!ex[j][i]))
            {
                a=v[i]; b=v[j];
                c.x=a.x+fabs(a.y-b.y);    c.y=a.y+fabs(a.x-b.x);
                cauta();
                ok=(p>0);   k=p;
                c.x=b.x+fabs(b.y-a.y);    c.y=b.y+fabs(b.x-a.x);
                if (ok)
                    cauta();
                ok=ok&(p>0);    q=p;
                if (ok)
                {
                    rez++;
                    ex[i][j]=ex[i][k]=ex[i][q]=ex[j][k]=ex[j][q]=ex[k][q]=1;
                }
            }
    printf("%ld",rez);
}

int main()
{
    freopen("patrate3.in","r",stdin);
    freopen("patrate3.out","w",stdout);
    citire();
    sort(v+1,v+1+n,cmp);
    rezolvare();
    return 0;
}