Cod sursa(job #1194598)

Utilizator PopescuMihai95Popescu Mihai PopescuMihai95 Data 4 iunie 2014 10:30:08
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,i,j,p,q,nr,m,k,st,dr;
double z,t;
struct nod
{
    double x;
    double y;
}v[1505];
int A,B,C,D,ok,sol;
int cmp(const nod a,const nod b)
{
    if (a.x==b.x) return a.y<=b.y;
    return a.x<b.x;
}
int cb(int A,int B)
{
    while (st<=dr)
        {
            m=(st+dr)/2;
            D=(v[m].y*1000); C=(v[m].x*1000);
            if (((A-C<=1)&&(B-D<=1))) return 1;
            if (A-C>1) {st=m+1; continue;}
            if ((A-C<=1)&&(B-D>1)) {st=m+1; continue;}
            if ((A-C<=1)&&(D-B>1)) {dr=m-1; continue;}
            if (C-A>1) {dr=m-1; continue;}
        }
        return 0;
}
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;
        if (cb(A,B)) sol++;
        else
        {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;
        if (cb(A,B)) sol++;
        }
    }
    printf("%d",sol/3);
    return 0;
}