Cod sursa(job #552503)

Utilizator ooctavTuchila Octavian ooctav Data 12 martie 2011 14:42:47
Problema Triang Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include<cmath>
#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;
const double s3 = sqrt((double)3)/2;

#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);*/
	}
}

II double modul(double x)
{
	if(x < 0)	return -x;
	return x;
}

II int compar(double X, double Y)
{
	if(modul(X - Y) < DIF)
		return 0;
	if((double)(X - Y) > 0)
		return -1;
	return 1;
}

II 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;
	REZ++;
	
	for(step = 1 ; REZ + step < N ; step <<= 1);
	for(; step ; step >>= 1)
		if(REZ + step <= N && compar(X.fs, a[REZ + step].fs) <= 0 && compar(X.sc, a[REZ + step].sc) <= 0)
			REZ += step;
		
	if(!compar(X.fs, a[REZ].fs) && !compar(X.sc, a[REZ].sc))	
		return 1;
	return 0;
}

void rezolva()
{
	FOR(i, 1, N)
		FOR(j, i + 1, N)
		{
			PDD C;
			
			C.fs = (a[i].fs/2 + s3*a[i].sc + a[j].fs/2 - s3*a[j].sc);
			C.sc = (-s3*a[i].fs + a[i].sc/2 + s3*a[j].fs + a[j].sc/2);
			if(caut_bin(C))	NR++;
			
			
			C.fs = (a[j].fs/2 + s3*a[j].sc + a[i].fs/2 - s3*a[i].sc);
			C.sc = (-s3*a[j].fs + a[j].sc/2 + s3*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;
}