Cod sursa(job #334614)

Utilizator DraStiKDragos Oprica DraStiK Data 27 iulie 2009 14:40:46
Problema Triang Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define EPS 0.001

vector <pair <double,double> > a;
double psin,pcos;
int n,nrt;

void read ()
{
    double x,y;
    int i;

    scanf ("%d",&n);
    for (i=1; i<=n; ++i)
    {
        scanf ("%lf%lf",&x,&y);
        a.pb (mp (x,y));
    }
}

double fabs (double a)
{
    if (a<0)
        return -a;
    return a;
}

int check (pair <double,double> a,pair <double,double> b)
{
    if (fabs (a.fs-b.fs)<EPS)
    {
        if (fabs (a.sc-b.sc)<EPS)
            return 0;
        else if (a.sc>b.sc)
            return -1;
        else
            return 1;

    }
    else if(a.fs>b.fs)
        return -1;
    else
        return 1;
}

int cbin (pair <double,double> p)
{
    int st,dr,mij,ok;

    for (st=0, dr=n-1; st<=dr; )
    {
        mij=(st+dr)/2;
        ok=check (p,a[mij]);
        if (!ok)
            return 1;
        else if (ok<0)
            st=mij+1;
        else
            dr=mij-1;
    }
    return 0;
}

void solve ()
{
    pair <double,double> p;
    int i,j;

    psin=(double)sqrt (3)/2;
    pcos=(double)1/2;
    for (i=0; i<n-1; ++i)
        for (j=i+1; j<n; ++j)
        {
            p.fs=(a[j].fs-a[i].fs)*pcos-(a[j].sc-a[i].sc)*psin+a[i].fs;
            p.sc=(a[j].fs-a[i].fs)*psin+(a[j].sc-a[i].sc)*pcos+a[i].sc;
            nrt+=cbin (p);
            p.fs=(a[i].fs-a[j].fs)*pcos-(a[i].sc-a[j].sc)*psin+a[j].fs;
            p.sc=(a[i].fs-a[j].fs)*psin+(a[i].sc-a[j].sc)*pcos+a[j].sc;
            nrt+=cbin (p);
        }
    printf ("%d",nrt/3);
}

int main ()
{
    freopen ("triang.in","r",stdin);
    freopen ("triang.out","w",stdout);

    read ();
    sort (a.begin (),a.end ());
    solve ();

    return 0;
}