Cod sursa(job #334618)

Utilizator DraStiKDragos Oprica DraStiK Data 27 iulie 2009 15:06:07
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <algorithm>
#include <math.h>
using namespace std;

#define DIM 1505
#define EPS 0.001

struct punct {double x,y;} a[DIM];
double psin,pcos;
int n,nrt;

inline void read ()
{
    int i;

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

inline int cmp (punct a,punct b)
{
    return a.x<b.x || (a.x==b.x && a.y<b.y);
}

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

inline int check (punct a,punct b)
{
    if (fabs (a.x-b.x)<EPS)
    {
        if (fabs (a.y-b.y)<EPS)
            return 0;
        else if (a.y>b.y)
            return -1;
        else
            return 1;

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

inline int cbin (punct p)
{
    int st,dr,mij,ok;

    for (st=1, dr=n; 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;
}

inline void solve ()
{
    punct p;
    int i,j;

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

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

    read ();
    sort (a+1,a+n+1,cmp);
    solve ();

    return 0;
}