Cod sursa(job #531169)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 8 februarie 2011 23:38:21
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<complex>
#define inf "triang.in"
#define outf "triang.out"
#define EPS 0.001
#define NMax 1600
using namespace std;

struct punct { double x,y; };
int N, nr;
punct P[NMax];

void read()
{
    scanf("%d", &N); double x,y;
    for(int i=1; i<=N; i++)
    {
        scanf("%lf%lf", &x, &y);
        P[i].x = x; P[i].y = y;
    }
}

struct cmp
{
    bool operator () (const punct &a, const punct &b) { return ( floor( a.x*1000 ) / 1000.0 ) < ( floor( b.x*1000 ) / 1000.0 ); }
};

bool cauta(double x, double y)
{
    int m, poz=0, st=1, dr=N, i;
    while( st<=dr )
    {
        m = (st+dr)>>1;
        if( fabs(P[m].x-x)<=EPS ) { poz = m; break; }
        if( ( floor( P[m].x*1000 ) / 1000.0 ) < ( floor( x*1000 ) / 1000.0 ) ) st = m+1;
        else dr = m-1;
    }
    if( !poz ) return false;
    i = poz;
    while( fabs(P[i].x-x)<=EPS && i<=N ) {
        if( fabs(P[i].y-y)<=EPS ) {  return true; }
        i++;
    }
    i = poz;
    while( fabs(P[i].x-x)<=EPS && i>=1 ) {
        if( fabs(P[i].y-y)<=EPS ) {  return true; }
        i--;
    }
    return false;
}

void solve()
{
    sort(P+1,P+N+1,cmp());
    //for(int i=1; i<=N; i++) printf("%lf %lf\n", P[i].x, P[i].y);
    complex<double> e( 1/2.0, sqrt(3)/2.0 );
    //printf("%.7lf %.7lf", e.real(), e.imag() );
    for(int i=1; i<N; i++)
        for(int j=i+1; j<=N; j++)
        {
            complex<double> a(P[i].x,P[i].y), b(P[j].x,P[j].y), aux(-1.0,0.0);
            complex<double> c1 = aux*(e*a + e*e*b);
            complex<double> c2 = aux*(e*e*a + e*b);
            //printf("%.7lf %.7lf\n", c1.imag(), c1.real() );
            //printf("%.7lf %.7lf\n", c2.imag(), c2.real() );
            if( cauta(c1.imag(), c1.real()) ) nr++;
            if( cauta(c2.imag(), c2.real()) ) nr++;
        }
    printf("%d",nr/2);
}

int main()
{
    freopen(inf,"r",stdin); freopen(outf,"w",stdout);
	read(); solve();
	return 0;
}