Cod sursa(job #1311151)

Utilizator akaprosAna Kapros akapros Data 7 ianuarie 2015 19:33:35
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,i,j,nr;
double e=0.0001,h,cx,cy,dx,dy;
double c1,c2;
struct punct
{
    double x;
    double y;
}v[1505];
int cb(int st,int dr)
{
    int m;
    st++; dr=n;
    while (st<=dr)
    {
        m=(st+dr)/2;
        if ((abs(v[m].x-cx)<e)&&(abs(v[m].y-cy)<e))
        return 1;
        if (abs(v[m].x-cx)<e)
        {
            if (v[m].y>cy) dr=m-1;
            else st=m+1;
        }
         if (v[m].x>cx) dr=m-1;
        else st=m+1;
    }
    return 0;
}
int cmp(const punct a,const punct b)
{
    if (a.x-b.y<e) return a.y<b.y;
    return a.x<b.x;
}
int main()
{
    freopen("triang.in","r",stdin);
    freopen("triang.out","w",stdout);
    scanf("%d",&n);
    h=0.866025;
    for (i=1;i<=n;i++)
    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++)
    {
        dx=v[j].x-v[i].x;
        dy=v[i].y-v[j].y;
        c1=(v[i].x+v[j].x)/2;
        c2=(v[i].y-v[j].y)/2;
        cx=c1+dy*h; cy=c2+dx*h;
        if (cb(i,j)) nr++;
        cx=c1-dy*h; cy=c2-dx*h;
        if (cb(i,j)) nr++;
    }
    printf("%d",nr);
    return 0;
}