Cod sursa(job #1073635)

Utilizator lianaliana tucar liana Data 6 ianuarie 2014 17:27:01
Problema Patrate 3 Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#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;
punct v[nmax], a, b, c;
bool ok, g;

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 (a.x!=b.x)
        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;
    }
    g=0;
    if ((st-1>=1)&&(eg(v[st-1],c)))
        g=1;
    if (eg(v[st],c))
        g=1;
    if ((st+1<=n)&&(eg(v[st+1],c)))
        g=1;

}

void rezolvare()
{
    for (i=1;i<=n;i++)
        for (j=i+1;j<=n;j++)
        {
            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=g;
            c.x=b.x+fabs(b.y-a.y);    c.y=b.y+fabs(b.x-a.x);
            cauta();
            ok=ok&g;
            rez+=ok;
        }
    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;
}