Cod sursa(job #1194576)

Utilizator PopescuMihai95Popescu Mihai PopescuMihai95 Data 4 iunie 2014 09:00:41
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,i,j,p,q,nr,m,k,st,dr;
double z,t;
int d(double a,double b,double c,double d)
{
    return ((a-c)*(a-c)+(b-d)*(b-d));
}
struct nod
{
    double x;
    double y;
}v[1505];
int cmp(const nod a,const nod b)
{
    if (a.x==b.x) return a.y<=b.y;
    return a.x<b.x;
}
int A,B,C,D,ok,sol;
int main()
{
    freopen("triang.in","r",stdin);
    freopen("triang.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        m=0;
        scanf("%lf %lf",&v[i].x,&v[i].y);
    }
    sort(v+1,v+n+1,cmp);
    for (i=1;i<n;i++)
    for (j=i+1;j<=n;j++)
    {
        z=(v[i].x+v[j].x)/2-(v[j].y-v[i].y)*0.866;
        t=(v[i].y+v[j].y)/2+(v[j].x-v[i].x)*0.866;
        z=z*1000; t=t*1000;
        A=z; B=t; ok=0;
        st=1; dr=n;
        while (st<=dr)
        {
            m=(st+dr)/2;
            D=(v[m].y*1000); C=(v[m].x*1000);
            if (((A==C)&&(B==D))) {ok=1; break;}
            if (A>C) {st=m+1; continue;}
            if ((A==C)&&(D<B)) {st=m+1; continue;}
            if ((A==C)&&(D>B)) {dr=m-1; continue;}
            if (C>A) {dr=m-1; continue;}
        }
        if (ok) sol++;
        if (!ok)
        {
        st=1; dr=n;
        z=(v[i].x+v[j].x)/2+(v[j].y-v[i].y)*0.866;
        t=(v[i].y+v[j].y)/2-(v[j].x-v[i].x)*0.866;
        z=z*1000; t=t*1000;
        A=z; B=t; ok=0;
        while (st<=dr)
        {
            m=(st+dr)/2;
            D=(v[m].y*1000); C=(v[m].x*1000);
            if (((A==C)&&(B==D))) {ok=1; break;}
            if (A>C) {st=m+1; continue;}
            if ((A==C)&&(D<B)) {st=m+1; continue;}
            if ((A==C)&&(D>B)) {dr=m-1; continue;}
            if (C>A) {dr=m-1; continue;}
        }
        }
    }
    printf("%d",sol);
    return 0;
}