Cod sursa(job #450227)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 8 mai 2010 00:11:29
Problema Triang Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.96 kb
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#define NMAX 1502
#define x first
#define y second
#define EPS 0.0001
#define MEPS -0.001
#define FIN "triang.in"
#define FOUT "triang.out"
#include<math.h>
#include<vector>
using namespace std;


int viz[NMAX][NMAX];

double abs(double a)
{
    if(a < EPS) return (-a);
    return a;
    }
const double  PI = 3.14159265;
int N,REZ;
double d[NMAX][NMAX];
pair<double,double> P[NMAX];
int comp(pair<double,double> a,pair<double,double> b)
{
    if( abs(a.x - b.x) < EPS ) return (a.y - b.y) < EPS;
    return (a.x - b.x) < EPS;
    }

int main()
{
    freopen(FIN,"r",stdin);
    freopen(FOUT,"w",stdout);
    scanf("%d",&N);
     for(int i = 1 ; i <= N ;i++ )
       scanf("%lf %lf",&P[i].x,&P[i].y);
    sort(P+1 , P + N + 1 , comp);   
    REZ = 0;
    int lg = 0;
    for(;(1<<lg) <= N;lg++);
    for(int i = 1 ;i<=N ; i++ )
     for(int j = i+1 ; j <= N ;j++)
      {
            pair<double,double> p1,p2;
            p1.x = cos(PI/3.0) * ( P[j].x - P[i].x) -  sin(PI/3.0) * (P[j].y - P[i].y) + P[i].x;
            p1.y = sin(PI/3.0) *  ( P[j].x - P[i].x) +  cos(PI/3.0) * (P[j].y - P[i].y) + P[i].y;
            p2.x = cos(5.0 * PI/3.0) * ( P[j].x - P[i].x) - sin(5.0 * PI/3.0) * (P[j].y - P[i].y) + P[i].x;
            p2.y = sin(5.0 * PI/3.0) * ( P[j].x - P[i].x) + cos(5.0 * PI/3.0) * (P[j].y - P[i].y) + P[i].y;
            int caut1 = N ;
            int boo = 0;
            for(int k = lg ;k >=0 ; k--)
              if( (caut1 - (1<<k)) > 0 && (p1.x - P[caut1 - (1<<k)].x) < EPS )
                   caut1 = caut1 - (1<<k);
            for(int k = lg ;k >=0 && !boo ; k--)
              if( (caut1 + (1<<k)) <= N && MEPS < p1.x - P[caut1 + (1<<k)].x && ( p1.x - P[caut1 + (1<<k)].x) < EPS && ( P[caut1 + (1<<k)].y - p1.y ) < EPS )
                  { caut1 = caut1 + (1<<k);
                  if(MEPS < p1.x - P[caut1].x && ( p1.x - P[caut1].x) < EPS && MEPS < p1.y - P[caut1].y && ( p1.y - P[caut1].y) < EPS) boo =1;
                  }
                  
            if((max(i,j)<caut1 &&  MEPS < p1.x - P[caut1].x) && ( p1.x - P[caut1].x) < EPS ) REZ++;
            caut1 = N ;
            boo = 0;
             boo = 0;
            for(int k = lg ;k >=0 ; k--)
              if( (caut1 - (1<<k)) > 0 && (p2.x - P[caut1 - (1<<k)].x) < EPS )
                   caut1 = caut1 - (1<<k);
            for(int k = lg ;k >=0 && !boo ; k--)
              if( (caut1 + (1<<k)) <= N && MEPS < p2.x - P[caut1 + (1<<k)].x && ( p2.x - P[caut1 + (1<<k)].x) < EPS && ( P[caut1 + (1<<k)].y - p2.y ) < EPS )
                  { caut1 = caut1 + (1<<k);
                  if(MEPS < p2.x - P[caut1].x && ( p2.x - P[caut1].x) < EPS && MEPS < p2.y - P[caut1].y && ( p2.y - P[caut1].y) < EPS) boo =1;
                  }
               
            if((max(i,j)<caut1 &&  MEPS < p2.x - P[caut1].x) && ( p2.x - P[caut1].x) < EPS ) REZ++;    }
     printf("%d",REZ);       
    
    return 0;    
    }