Cod sursa(job #973115)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 13 iulie 2013 15:08:36
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<fstream>
#include<cmath>
#include<set>
#define pdd pair<double,double>
#define EPS 0.001
using namespace std;
int n;
long long sol;
struct Punct{double x,y;};
Punct P[1510],D;
set <pdd> S;

inline int Count(Punct A,Punct B)
{
	Punct C;
	pdd c;
	C.x=A.x+D.x*(B.x-A.x)-D.y*(B.y-A.y);
	C.y=A.y+D.y*(B.x-A.x)+D.x*(B.y-A.y);
	c=*S.lower_bound(make_pair(C.x-EPS,C.y-EPS));
	if(fabs(C.x-c.first)<=EPS && fabs(C.y-c.second)<=EPS)
		return 1;
	return 0;
}

int main()
{
	int i,j;
	ifstream fin("triang.in");
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>P[i].x>>P[i].y;
		S.insert(make_pair(P[i].x,P[i].y));
	}
	fin.close();
	
	D.x=cos(M_PI/3.0);
	D.y=sin(M_PI/3.0);
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
			sol+=1LL*Count(P[i],P[j])+1LL*Count(P[j],P[i]);
	sol/=3LL;
	
	ofstream fout("triang.out");
	fout<<sol<<"\n";
	fout.close();
	return 0;
}