Cod sursa(job #1740262)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 11 august 2016 12:28:58
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <bits/stdc++.h>

#define NMax 1501
#define eps 0.001
using namespace std;
ifstream f("triang.in");
ofstream g("triang.out");
struct point{
    double x,y;
};

point p[NMax];
int n,ans;

bool cmp(point x, point y){
    if(x.x < y.x)
        return 1;
    return 0;
}

int caut(int lo,int hi, double x, double y){
    int mij = (lo + hi) / 2;
    while(lo <= hi){
        mij = (lo + hi) / 2;
        if(fabs(p[mij].x - x) <= eps && fabs(p[mij].y - y) <= eps){
            return 1;
        }
        if(p[mij].x - x >= eps){
            hi = mij - 1;
        }else{
            lo = mij + 1;
        }
    }
    return 0;
}
int main()
{
    f >> n;
    for(int i = 1; i <= n; ++i)
        f >> p[i].x >> p[i].y;
    sort(p + 1, p + 1 + n,cmp);

    double cos = (double)1/2;
    double sin = (double)(sqrt(3))/2;
    double sin2 = -sin;

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