Cod sursa(job #1065569)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 23 decembrie 2013 14:37:50
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;

struct Point
{
    double x,y;
};

int N,sol;
Point P[1005],B,D;

inline double dist(Point A,Point B)
{
    return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}

inline bool equals(double A,double B)
{
    if(fabs(A-B)<=0.00001) return 1;
    return 0;
}

inline bool cmp(Point A,Point B)
{
    if(equals(A.x,B.x)) return (A.y<B.y);
    return (A.x<B.x);
}

void determine(int i,int j)
{
    double mAC,mBD,nBD,d,a,b,c;
    Point M;
    M.x=(P[i].x+P[j].x)/2;
    M.y=(P[i].y+P[j].y)/2;
    if(P[i].x != P[j].x && P[i].y != P[j].y)
    {
        mAC=(P[i].y-P[j].y)/(P[i].x-P[j].x);
        mBD=-1/mAC;
        a=mAC;
        b=-1;
        c=P[i].y-mAC*P[i].x;
        d=dist(P[i],M)*sqrt(a*a+b*b);
        nBD=M.y-mBD*M.x;
        B.x=(d-b*nBD-c)/(a+b*mBD);
        B.y=mBD*B.x+nBD;
        D.x=(-d-b*nBD-c)/(a+b*mBD);
        D.y=mBD*D.x+nBD;
        return;
    }
    if(P[i].x == P[j].x)
    {
        d=dist(P[i],M);
        B.x=M.x-d;
        B.y=M.y;
        D.x=M.x+d;
        D.y=M.y;
        return;
    }
    if(P[i].y == P[j].y)
    {
        d=dist(P[i],M);
        B.x=M.x;
        B.y=M.y-d;
        D.x=M.x;
        D.y=M.y+d;
        return;
    }
}

bool binary_s(Point A)
{
    int st=1,dr=N,md;
    for(; st<=dr;)
    {
        md=(st+dr)/2;
        if(equals(A.x,P[md].x) && equals(A.y,P[md].y)) return 1;
        if(cmp(A,P[md])) dr=md-1;
        else st=md+1;
    }
    return 0;
}

int main()
{
    int i,j;
    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)
        {
            determine(i,j);
            if(binary_s(B) && binary_s(D)) ++sol;
        }
    printf("%d\n",sol/2);
    return 0;
}