Cod sursa(job #945611)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 2 mai 2013 12:56:32
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include<stdio.h>
#include<cmath>
#include<algorithm>
#define Nmx 1505
#define EPS 0.001


using namespace std;

struct coord
{
    double x,y;
};
coord a[Nmx];
int n;


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

inline int cmp (coord a,coord 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(coord a,coord 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;
}


int caut(int st,int dr,coord p)
{
    while(st<=dr)
    {
        int mij=(st+dr)>>1;
        int ok=check (p,a[mij]);
        if (!ok)
            return 1;
        else if (ok<0)
            st=mij+1;
        else
            dr=mij-1;
    }
    return 0;
}

void solve()
{
    int nr=0;
    double psin=(double)sqrt (3)/2;
    double pcos=(double)1/2;
    coord p;
    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[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;
            nr+=caut(j+1,n,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;
            nr+=caut(j+1,n,p);
        }
    printf("%d\n",nr);
}

int main()
{
    freopen("triang.in","r",stdin);
    freopen("triang.out","w",stdout);
    citire();
    solve();
    return 0;
}