Pagini recente » Cod sursa (job #228509) | Cod sursa (job #1423310) | Cod sursa (job #1440427) | Cod sursa (job #2199382) | Cod sursa (job #450215)
Cod sursa(job #450215)
#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( (caut2 | (1<<k)) <= N && (P[(caut2 | (1<<k))].x - p1.x) < EPS ) caut2 = caut2 | (1<<k);
if( (cautp2 | (1<<k)) <= N && (P[(cautp2 | (1<<k))].x - p2.x) < EPS ) cautp2 = cautp2 | (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;
}