Cod sursa(job #1291404)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 12 decembrie 2014 19:15:42
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<fstream>
#include<cmath>
#include<algorithm>
using namespace std;
ifstream f("triang.in"); ofstream g("triang.out");
double ep=0.001;
double si=1.7320508/2, co=0.5;
struct pct {double x,y;} p,a[1501];
int n,nr;
bool cmp(pct a,pct b)
{   return ((b.x-a.x>ep) || ((fabs(b.x-a.x)<ep) && (b.y-a.y>ep)));}
int cautare(pct b)
{   int m,p=1,u=n;
    while(p<=u)
    {   m=(p+u)/2;
        if((fabs(a[m].x-b.x)<ep) && (fabs(a[m].y-b.y)<ep)) return m;
            else if(cmp(a[m],b)) p=m+1; else u=m-1;
    }
    return 0;
}
int main()
{   f>>n;
    for(int i=1;i<=n;i++) f>>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(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++;
        }
    g<<nr<<'\n'; g.close(); return 0;
}