Cod sursa(job #2098251)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 2 ianuarie 2018 16:41:04
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
/// #bettercoderthanshebeautiful
#include<cstdio>
#include<cmath>
#include<algorithm>
#define eps 1e-3
#define sq3 1.7320508
using namespace std;
int n,sol;
struct points
{
    double x,y;
};
points v[1502];
bool eq(double a, double b)
{
    if(a-b<eps)
        return 1;
    return 0;
}
bool test(points a, points b)
{
    if(eq(a.x,a.y))
        return a.y<b.y;
    return a.x<b.x;
}
points cw(double xa, double ya, double xb, double yb)
{
    swap(xa,ya);
    xa*=-1.00000;
    xa+=xb;
    ya+=yb;
    return {xa,ya};
}
points ccw(double xa, double ya, double xb, double yb)
{
    swap(xa,ya);
    ya*=-1.00000;
    xa+=xb;
    ya+=yb;
    return {xa,ya};
}
bool binsearch(points a)
{
    int b=1;
    int e=n;
    while(b<=e)
    {
        int m=(b+e)/2;
        if(eq(v[m].x,a.x) && eq(v[m].y,a.y))
            return 1;
        else
            if(v[m].x-a.x>eps || eq(v[m].x,a.x) && v[m].y-a.y>eps)
                e=m-1;
            else
                b=m+1;
    }
    return 0;
}
void calculations(points a, points b)
{
    double Xmid=0.50000*(a.x+b.x);
    double Ymid=0.50000*(a.y+b.y);
    double difa=(b.x-Xmid)*sq3;
    double difb=(b.y-Ymid)*sq3;
    points x=cw(difa, difb,Xmid, Ymid);
    points y=ccw(difa, difb, Xmid, Ymid);
    sol+=binsearch(x)+binsearch(y);
}
int main()
{
    freopen("triang.in", "r", stdin);
    freopen("triang.out", "w", stdout);
    scanf("%d\n",&n);
    for (int i = 1; i <= n; i++)
        scanf("%lf %lf\n", &v[i].x, &v[i].y);
    sort(v+1,v+n+1,test);
    sol=0;
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
            calculations(v[i],v[j]);
    printf("%d",sol/3);
    return 0;
}