Cod sursa(job #1082905)

Utilizator leontinLeontin leontin Data 15 ianuarie 2014 01:27:31
Problema Stramosi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

double eps=0.0001, va1=0.8660254, va2=0.5;

struct point
{
    double x;
    double y;
};
point a[1501],p;

bool compare(point a,point b)
{
    return ((b.x-a.x>eps) || ((fabs(b.x-a.x)<eps) && (b.y-a.y>eps)));
}

int n;

int search(point b)
{
    int m;
    int st=1,dr=n;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if((fabs(a[m].x-b.x)<eps) && (fabs(a[m].y-b.y)<eps))
            return m;
        else if(compare(a[m],b))
            st=m+1;
        else dr=m-1;
    }
    return 0;
}
int main()
{
    int i,j;
    ifstream f("triang.in");
    ofstream g("triang.out");
    f>>n;
    for(i=1; i<=n; i++)
    {
        f>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1,compare);

    int nr=0;
    for(i=1; i<n; i++)
        for(j=i+1; j<=n; j++)
        {
            p.x=a[i].x+(a[j].x-a[i].x)*va2-(a[j].y-a[i].y)*va1;
            p.y=a[i].y+(a[j].x-a[i].x)*va1+(a[j].y-a[i].y)*va2;

            if(search(p)>j)
                nr++;
            p.x=a[i].x+(a[j].x-a[i].x)*va2+(a[j].y-a[i].y)*va1;
            p.y=a[i].y-(a[j].x-a[i].x)*va1+(a[j].y-a[i].y)*va2;
            if(search(p)>j)
                nr++;
        }
    g<<nr;
    return 0;
}