Cod sursa(job #1311121)

Utilizator akaprosAna Kapros akapros Data 7 ianuarie 2015 19:06:17
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int n,i,j,nr;
double e=0.0001,h;
struct punct
{
    double x;
    double y;
}v[1505];
double d(double x1,double yy1,double x2,double y2)
{
    double t1,t2;
    t1=(x1-x2)*(x1-x2);
    t2=(yy1-y2)*(yy1-y2);
    return t1+t2;
}
int cb(int st,int dr)
{
    int m;
    double c1,c2,l,D;
    c1=(v[i].x+v[j].x)/2;
    c2=(v[i].y-v[j].y)/2;
    l=d(v[i].x,v[i].y,v[j].x,v[j].y);
    st++; dr--;
    while (st<=dr)
    {
        m=(st+dr)/2;
        D=d(c1,c2,v[m].x,v[m].y);
        if (D-l*h<e)
        return 1;
        if (D<l*h) 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.75000;
    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++)
    if (cb(i,j)) nr++;
    printf("%d",nr);
    return 0;
}