Cod sursa(job #407245)

Utilizator loginLogin Iustin Anca login Data 2 martie 2010 10:26:01
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
# include <fstream>
# include <iostream>
# include <algorithm>
# include <cmath>
# define EPS 0.001
# define PI 3.14159265
using namespace std;
struct pct {
	double x, y;
	friend bool operator < (const pct &a, const pct &b)
	{
		if (a.x<b.x || (abs(a.x-b.x)<=1e-3 && a.y+EPS<b.y))
			return 1;
		return 0;
	};
};

int n;
long long int sol;
pct v[1503];

void read ()
{
	ifstream fin ("triang.in");
	fin>>n;
	for (int i=1;i<=n;i++)
		fin>>v[i].x>>v[i].y;
}

int cmp (pct a, pct b)
{
	if (a.x+EPS<b.x)
		return -1;
	if (a.x-b.x>-EPS && a.x-b.x<EPS && a.y+EPS<b.y)
		return -1;
	if (a.x-b.x>-EPS && a.x-b.x<EPS && a.y-b.y>-EPS && a.y-b.y<EPS)
		return 0;
	return 1;
}

int cauta (int st, int dr, pct p)
{
	if (st>dr)
		return 0;
	if (st==dr)
	{
		if (cmp(v[st], p)==0)
			return 1;
		return 0;
	}
	int m=(st+dr)/2;
	if (cmp(v[m],p)==0)
			return 1;
	if (cmp(p, v[m])==-1)
		return cauta (st, m, p);
	return cauta (m+1, dr, p);
}

pct punct (int i, int j)
{
	pct p1;
	p1.x=cos(PI/3)*(v[j].x-v[i].x)-sin(PI/3)*(v[j].y-v[i].y)+v[i].x;
	p1.y=sin(PI/3)*(v[j].x-v[i].x)+cos(PI/3)*(v[j].y-v[i].y)+v[i].y;
	return p1;
}

void solve ()
{
	pct p1, p2;
	for (int i=1;i<n;i++)
		for (int j=i+1;j<=n;j++)
		{
			p1=punct(j, i);
//			p2=punct(j, i);
			if(cauta(j+1, n, p1))
				sol++;
	//		if(cauta(i, n, p2))
		//		sol++;
		}
}

int main ()
{
	read ();
	sort (v+1, v+n+1);
	solve ();
	ofstream fout ("triang.out");
	fout<<sol;
	return 0;
}