Cod sursa(job #1318076)

Utilizator sanzianaioneteIonete Sanziana sanzianaionete Data 15 ianuarie 2015 15:58:58
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.61 kb
#include<fstream>
#include<algorithm>
#include<cmath>
using namespace std;
ifstream f("patrate3.in");
ofstream g("patrate3.out");
int n,nr=0;
double e=0.0001;
struct pct
{
    double x,y;
}a[1003];
bool eq(pct p1, pct p2)
{
    if(fabs(p1.x-p2.x)<e&&fabs(p1.y-p2.y)<e)
        return true;
    return false;
}
bool cmp(pct p1,pct p2)
{
    if(p1.x==p2.x)
        return p1.y<p2.y;
    else
        return p1.x<p2.x;
}
bool cb(pct p,int s,int d)
{
     int m=(s+d)/2;
     if(s>=d)
        return false;
     if(eq(a[m],p))
        return true;
     if(fabs(p.x-a[m].x)>=e)
     {
         if(p.x<a[m].x)
            return cb(p,s,m);
         else
            return cb(p,m+1,d);
     }
     else
     {
         if(p.y<a[m].y)
            return cb(p,s,m);
         else
            return cb(p,m+1,d);
     }
}
int main()
{
    f>>n;
    for(int i=0;i<n;++i)
        f>>a[i].x>>a[i].y;
    sort(a,a+n,cmp);
    for(int i=0;i<n-1;++i)
        for(int j=i+1;j<n;++j)
        {
            double x1=(a[i].x+a[j].x)/2,y1=(a[i].y+a[j].y)/2,x2=fabs(a[i].x-a[j].x)/2,y2=fabs(a[i].y-a[j].y)/2;
            pct p1,p2;
            if(a[i].y<a[j].y)
            {
                p1.x=x1+y2;p1.y=y1-x2;
                p2.x=x1-y2;p2.y=y1+x2;
                if(cb(p1,0,n)&&cb(p2,0,n))
                    nr++;
            }
            else
            {
                p1.x=x1+y2;p1.y=y1+x2;
                p2.x=x1-y2;p2.y=y1-x2;
                if(cb(p1,0,n)&&cb(p2,0,n))
                    nr++;
            }
        }
    g<<nr/2;
    f.close();g.close();
    return 0;
}