Cod sursa(job #1322221)

Utilizator ThomasFMI Suditu Thomas Thomas Data 19 ianuarie 2015 21:15:09
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
struct punct {double x,y;} P[1001];
int n,i,j,k;
double x1,x2,y12,y2,xm,ym;
 
int c(double a, double b)
{
    if(b-a > 0.00001) return 1;
    if(a-b > 0.00001) return -1;
    if(fabs(a-b) < 0.00001) return 0;
}
 
int caut(double x, double y)
{
    int st = 1, dr = n, m;
    while(st < dr)
    {
       m = (st+dr)/2;
       if(c(x,P[m].x)==0 && c(y,P[m].y)==0) return 1;
       if(c(x,P[m].x)>0 || (c(x,P[m].x) == 0 && c(y,P[m].y)>0)) dr = m-1;
       else
       if(c(x,P[m].x)<0 || (c(x,P[m].x)==0 && c(y,P[m].y)<0)) st = m + 1;
    }
    return ((c(P[m].x, x)==0 && c(P[m].y,y)==0) || (c(P[m-1].x, x)==0 && c(P[m-1].y,y)==0) || (c(P[m+1].x, x)==0 && c(P[m+1].y,y)==0));
}
 
int cmp(punct a, punct b)
{
    if(a.x < b.x) return 1;
    if(a.x > b.x) return 0;
    return(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",&P[i].x, &P[i].y);
    sort(P+1, P+n+1, cmp);
    for(i=1; i<n; ++i)
        for(j=i+1; j<=n; ++j)
        {
            xm = (P[i].x + P[j].x)/2;
            ym = (P[i].y + P[j].y)/2;
            x1 = xm - (P[i].y - ym);
            y12 = ym + (P[i].x - xm);
            x2 = xm - (P[j].y - ym);
            y2 = ym + (P[j].x - xm);
            if(caut(x1,y12))
                if(caut(x2,y2))
                    ++k;
        }
    printf("%d\n",k/2);
    return 0;
}