Cod sursa(job #1751851)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 2 septembrie 2016 04:54:11
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
///Nu se merita... Nu se merita!
#include<cstdio>
#include<algorithm>
#define MAXN 1510
#define EPS 1e-3
#define cos 0.5
#define sin 0.8660254
using namespace std;
int n;
struct Point{
    double x;
    double y;
};
Point v[MAXN];
bool Compare(Point a,Point b){
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}
int BinarySearch(int left,int right,double x,double y){
    int middle;
    while(left<=right){
        middle=(left+right)/2;
        if(fabs(x-v[middle].x)<EPS&&fabs(y-v[middle].y)<EPS)
            return 1;
        if(v[middle].x<x)
            left=middle+1;
        else
            right=middle-1;
    }
    return 0;
}
int main(){
    freopen("triang.in","r",stdin);
    freopen("triang.out","w",stdout);
    int i,j,answer=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%lf%lf",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,Compare);
    for(i=1;i<=n-2;i++)
        for(j=i+1;j<=n-1;j++){
            answer+=BinarySearch(j+1,n,(v[i].x+v[j].x)*cos+(v[i].y-v[j].y)*sin,(v[j].x-v[i].x)*sin+(v[j].y+v[i].y)*cos);
            answer+=BinarySearch(j+1,n,(v[i].x+v[j].x)*cos+(v[j].y-v[i].y)*sin,(v[i].x-v[j].x)*sin+(v[j].y+v[i].y)*cos);
        }
    printf("%d",answer);
    return 0;
}