Cod sursa(job #1744948)

Utilizator antanaAntonia Boca antana Data 20 august 2016 19:13:26
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <cstdio>
#include<algorithm>
#include<cmath>
#define MAXN 1500
#define EPS 0.0001
#define cos 0.5
#define sin 0.8660254

struct aa{
    double x, y;
}p[MAXN+1];

int n, ans;

bool cmp(const aa &a, const aa &b)
{
    if(a.x == b.x) return (a.y < b.y);
    return (a.x < b.x);
}

inline int cauta(int st, int dr, double x, double y)
{
    int m;

    while(st<=dr)
    {
        m=(st+dr)/2;
        if(fabs(p[m].x - x) < EPS && fabs(p[m].y - y) < EPS)
            return 1;
        if(fabs(p[m].x - x) < EPS)
        {
            if(p[m].y < y)
                st=m+1;
            else dr=m-1;
        }
        if(p[m].x < x)
            st=m+1;
        else dr=m-1;
    }

    return 0;
}

int main()
{
    freopen("triang.in", "r", stdin);
    freopen("triang.out", "w", stdout);

    scanf("%d", &n);

    for(int i=1;i<=n;++i)
        scanf("%lf%lf", &p[i].x, &p[i].y);

    std::sort(p+1, p+n+1, cmp);

    for(int i=1;i<n-1;++i)
        for(int j=i+1;j<n;++j)
        {
            ans+=cauta(j+1, n, (p[i].x+p[j].x)*cos+(p[i].y-p[j].y)*sin, (p[j].x-p[i].x)*sin+(p[j].y+p[i].y)*cos);
            ans+=cauta(j+1, n, (p[i].x+p[j].x)*cos+(p[j].y-p[i].y)*sin, (p[i].x-p[j].x)*sin+(p[j].y+p[i].y)*cos);
        }

    printf("%d", ans);

    return 0;
}