Cod sursa(job #1048347)

Utilizator the@EyE@Postavaru Stefan the@EyE@ Data 5 decembrie 2013 19:12:37
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#define ER 0.0001

using namespace std;

struct point
{
    double x,y;
};

bool eq(point p1, point p2)
{
    if(fabs(p1.x-p2.x)<ER&&fabs(p1.y-p2.y)<ER)return true;
    return false;
}

bool eqD(double d1,double d2)
{
    if(fabs(d1-d2)<ER)return true;
    return false;
}

bool cmp(point p1,point p2)
{
    if(p1.x==p2.x)return p1.y<p2.y;
    else return p1.x<p2.x;
}

vector<point> points;
int n,ras=0;

bool search(point p,int st,int dr)
{
     int m=(st+dr)/2;
     if(m>=n)return false;
     if(eq(points[m],p))return true;
     if(st==dr)return false;
     if(!eqD(p.x,points[m].x))
     {
         if(p.x<points[m].x)return search(p,st,m);
         else return search(p,m+1,dr);
     }
     else
     {
         if(p.y<points[m].y)return search(p,st,m);
         else return search(p,m+1,dr);
     }
}

int main()
{
    freopen("patrate3.in","r",stdin);
    freopen("patrate3.out","w",stdout);
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        point p;
        scanf("%lf%lf",&p.x,&p.y);
        points.push_back(p);
    }
    sort(points.begin(),points.end(),cmp);
    for(int i=0;i<n-1;++i)
        for(int j=i+1;j<n;++j)
        {
            point p1=points[i];point p2=points[j];
            double dy=fabs(p1.y-p2.y)/2;double cy=(p1.y+p2.y)/2;
            double dx=fabs(p1.x-p2.x)/2;double cx=(p1.x+p2.x)/2;
            if(p1.y<p2.y)
            {
                point p3;p3.x=cx+dy;p3.y=cy-dx;
                point p4;p4.x=cx-dy;p4.y=cy+dx;
                if(search(p3,0,n)&&search(p4,0,n))ras++;
            }
            else
            {
                point p3;p3.x=cx+dy;p3.y=cy+dx;
                point p4;p4.x=cx-dy;p4.y=cy-dx;
                if(search(p3,0,n)&&search(p4,0,n))ras++;
            }
        }
    printf("%d\n",ras/2);

    return 0;
}