Cod sursa(job #450214)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 7 mai 2010 22:49:53
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.73 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 , caut2 = 0 , cautp1 = N , cautp2 = N;
            for(int k = lg ;k >=0 ; k--)
                  {if( (caut1 - (1<<k)) > 0 && (p1.x - P[caut1 - (1<<k)].x) < EPS  ) caut1 = caut1 - (1<<k);
                   if( (cautp1 - (1<<k)) > 0 && (p2.x - P[cautp1 - (1<<k)].x) < EPS  ) cautp1 = cautp1 - (1<<k);
                 }
            for(int k = lg ;k >=0 ; k--)
               {if( (caut1 - (1<<k)) > 0 && (p1.x - P[caut1 - (1<<k)].x) < EPS  ) caut1 = caut1 - (1<<k);
                if( (cautp2 | (1<<k)) <= N && (P[(cautp2 | (1<<k))].x - p2.x) < EPS  ) cautp2 = cautp2 | (1<<k);
            }
            for(int k = lg ;k >= 0 ; k--)   
               if( (caut2 | (1<<k)) <= N && (P[(caut2 | (1<<k))].x - p1.x) < EPS  ) caut2 = caut2 | (1<<k);
             if( MEPS < ( p1.x - P[caut1].x) && ( p1.x - P[caut1].x) < EPS && MEPS < (p1.x - P[caut2].x)&& (p1.x - P[caut2].x) < EPS ) 
            { if(caut1 == caut2) {if(max(i,j)<caut1 && MEPS<(p1.y - P[caut1].y) && (p1.y - P[caut1].y)<EPS) REZ++;}
             else {
                    int caut = caut1,SUP = 0;
                    for(;(1<<SUP)<=(caut2 - caut1);SUP++);
                    for(int k = SUP ; caut <= caut2 , k>=0 ; k--)
                     {
                        if(caut+(1<<k) <= caut2 && (P[caut+(1<<k)].y - p1.y) < EPS)  caut = caut + (1<<k);    
                            }
                            
                    if(max(i,j)<caut && MEPS <(p1.y - P[caut].y) && (p1.y - P[caut].y)<EPS) REZ++;}}
             
             if( MEPS < ( p2.x - P[cautp1].x) && ( p2.x - P[cautp1].x) < EPS && MEPS < (p2.x - P[cautp2].x)&& (p2.x - P[cautp2].x) < EPS ) 
            { if(cautp1 == cautp2) {if(max(i,j)<cautp1 && MEPS<(p2.y - P[cautp1].y) && (p2.y - P[cautp1].y)<EPS) REZ++;}
             else {
                    int caut = cautp1,SUP = 0;
                    for(;(1<<SUP)<=(cautp2 - cautp1);SUP++);
                    for(int k = SUP ; caut <= cautp2 , k>=0 ; k--)
                     {
                        if(caut+(1<<k) <= cautp2 && (P[caut+(1<<k)].y - p2.y) < EPS)  caut = caut + (1<<k);    
                            }
                    if(max(i,j)<caut && MEPS < (p2.y - P[caut].y) && (p2.y - P[caut].y) < EPS) REZ++;}}
                    
                    }
     printf("%d",REZ);       
    
    return 0;    
    }