Cod sursa(job #1021909)

Utilizator mazaandreiAndrei Mazareanu mazaandrei Data 4 noiembrie 2013 14:32:22
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<fstream>
#include<algorithm>
using namespace std;
const double eps=0.0001;
int n,nr;
struct punct{ double x, y;} a[2000],p;
ifstream in("triang.in"); ofstream out("triang.out");
double si=1.7320508/2, co=0.5;
double mod( double x){ if(x<0) return -x; return x;}
struct cmp{
    bool operator()(const punct &a, const punct &b){
        if(a.x-b.x<eps || (mod(a.x-b.x)<eps && a.y-b.y<eps)) return 0;
        return 1;
    };
};
int cautare(punct b){
    int m,p=1,u=n;
    while(p<=u){
        m=(p+u)/2;
        if((mod(a[m].x-b.x)<eps) && (mod(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+nr+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(cautare(p)>j) nr++;
            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(cautare(p)>j) nr++;
        }
    }
    out<<nr<<'\n';
    out.close(); return 0;
}