Cod sursa(job #1021919)

Utilizator mazaandreiAndrei Mazareanu mazaandrei Data 4 noiembrie 2013 14:43:15
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<fstream>
#include<cmath>
#include<algorithm>
using namespace std;
ifstream in("triang.in"); ofstream out("triang.out");
double eps=0.001;
double si=0.8660254, co=0.5;
struct punct {double x,y;} p,a[1501];
int n,sol;
bool cmp(punct a,punct b){   return ((b.x-a.x>eps) || ((fabs(b.x-a.x)<eps) && (b.y-a.y>eps)));}
int bsearch(punct b){
    int m,p=1,u=n;
    while(p<=u){
        m=(p+u)/2;
        if((fabs(a[m].x-b.x)<eps) && (fabs(a[m].y-b.y)<eps)) return m;
            else if(cmp(a[m],b)) p=m+1; else u=m-1;
    }
    return 0;
}
int main(){
    in>>n;
    for(int i=1;i<=n;i++) in>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++){
            p.x=a[i].x+(a[j].x-a[i].x)*co-(a[j].y-a[i].y)*si;
            p.y=a[i].y+(a[j].x-a[i].x)*si+(a[j].y-a[i].y)*co;
            if(bsearch(p)>j) sol++;
            p.x=a[i].x+(a[j].x-a[i].x)*co+(a[j].y-a[i].y)*si;
            p.y=a[i].y-(a[j].x-a[i].x)*si+(a[j].y-a[i].y)*co;
            if(bsearch(p)>j) sol++;
    }
    out<<sol<<'\n'; out.close(); return 0;
}