Mai intai trebuie sa te autentifici.
Cod sursa(job #552468)
Utilizator | Data | 12 martie 2011 13:37:29 | |
---|---|---|---|
Problema | Triang | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.42 kb |
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<deque>
#include<queue>
#include<set>
#include<vector>
using namespace std;
const char IN[] = {"triang.in"};
const char OUT[] = {"triang.out"};
const int INF = 1000000005;
const double PI = 3.14159265;
const int NMAX = 1505;
const double ALFA = 0.01;
const double DIF = 0.001;
#define II inline
#define LL long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define FOR(i, a, b) for(int i = a ; i <= b ; i++)
#define IFOR(i, a, b) for(int i = a ; i >= b ; i--)
#define FORIT(it, V) for(vector<int> :: iterator it = V.begin() ; it != V.end() ; it++)
#define all(a) a, a +
int N;
PDD a[NMAX];
PDD p1, p2;
int NR;
void citi()
{
scanf("%d", &N);
FOR(i, 1, N)
{
scanf("%lf%lf", &a[i].fs, &a[i].sc);
/*double x, y;
x = a[i].fs*cos(ALFA) - a[i].sc*sin(ALFA);
y = a[i].fs*sin(ALFA) + a[i].sc*cos(ALFA);
a[i] = mp(x, y);*/
}
}
inline int compar(double X, double Y)
{
if(abs(X - Y) < DIF)
return 0;
if((double)(X - Y) > 0)
return -1;
return 1;
}
bool caut_bin(PDD X)
{
int REZ = 0, step;
for(step = 1 ; step < N ; step <<= 1);
for(; step ; step >>= 1)
if(REZ + step <= N && compar(X.fs, a[REZ + step].fs) <= 0)
REZ += step;
for(step = 1 ; step < N ; step <<= 1);
for(; step ; step >>= 1)
if(REZ + step <= N && compar(X.sc, a[REZ + step].sc) <= 0)
REZ += step;
//if(REZ - 1 > 0 && !compar(X, a[REZ - 1])) return 1;
if(compar(X.fs, a[REZ].fs) && compar(X.sc, a[REZ].sc)) return 1;
//if(REZ + 1 <= N && !compar(X, a[REZ + 1])) return 1;
return 0;
}
void rezolva()
{
FOR(i, 1, N)
FOR(j, i + 1, N)
{
PDD C;
C.fs = (a[i].fs/2 + sqrt((double)3)/2*a[i].sc + a[j].fs/2 - sqrt((double)3)/2*a[j].sc);
C.sc = (-sqrt((double)3)/2*a[i].fs + a[i].sc/2 + sqrt((double)3)/2*a[j].fs + a[j].sc/2);
if(caut_bin(C)) NR++;
C.fs = (a[j].fs/2 + sqrt((double)3)/2*a[j].sc + a[i].fs/2 - sqrt((double)3)/2*a[i].sc);
C.sc = (-sqrt((double)3)/2*a[j].fs + a[j].sc/2 + sqrt((double)3)/2*a[i].fs + a[i].sc/2);
if(caut_bin(C)) NR++;
}
}
void scrie()
{
printf("%d\n", NR/3);
}
int main()
{
freopen(IN, "r", stdin);
freopen(OUT, "w", stdout);
citi();
sort(a + 1, a + N + 1);
rezolva();
scrie();
return 0;
}