Cod sursa(job #345868)

Utilizator AndreyPAndrei Poenaru AndreyP Data 5 septembrie 2009 11:41:14
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<set>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pdd pair<double,double>
#define N 1510
const double eps=1e-4;
const double eps1=1e-3;
struct classcomp
{
	bool operator() (const pdd &x,const pdd &y) const
	{
		if(x.fs+eps1<y.fs)
			return true;
		if(y.fs+eps1<x.fs)
			return false;
		if(x.sc+eps1<y.sc)
			return true;
		return false;
	}
}; 
int n;
pdd v[N];
set<pdd,classcomp> s;
int rez;
inline char cmp(double x,double y)
{
	if(x+eps<y)
		return -1;
	if(y+eps<x)
		return 1;
	return 0;
}
inline void citire()
{
	scanf("%d",&n);
	for(int i=0; i<n; ++i)
	{
		scanf("%lf%lf",&v[i].fs,&v[i].sc);
		s.insert(v[i]);
	}
}
inline void vezi(const pdd &p1,const pdd &p2)
{
	double A=p2.sc-p1.sc;
	double B=p1.fs-p2.fs;
	double C=p2.fs*p1.sc-p1.fs*p2.sc;
	double d12=sqrt((p1.fs-p2.fs)*(p1.fs-p2.fs)+(p1.sc-p2.sc)*(p1.sc-p2.sc));
	double d=d12*sqrt(3)/2;

	double A1=B;
	double B1=-A;
	pdd pm=mp((p1.fs+p2.fs)/2,(p1.sc+p2.sc)/2);
	double C1=-A1*pm.fs-B1*pm.sc;

        if(cmp(A,0)==0)
	{
        	pdd cine;
                cine.fs=pm.fs;
		cine.sc=p1.sc+d;
		if(s.find(cine)!=s.end())
			++rez;
		cine.sc=p1.sc-d;
		if(s.find(cine)!=s.end())
			++rez;
		return;
	}

        if(cmp(B,0)==0)
	{
		pdd cine;
		cine.sc=pm.sc;
		cine.fs=p1.fs+d;
		if(s.find(cine)!=s.end())
			++rez;
		cine.fs=p1.fs-d;
		if(s.find(cine)!=s.end())
			++rez;
		return;
	}

	double con=sqrt(A*A+B*B)*d;
	pdd cine;
	cine.fs=(C1/B1+(con-C)/B)/(A/B-A1/B1);
	cine.sc=-(A1/B1*cine.fs+C1/B1);
	if(s.find(cine)!=s.end())
		++rez;
        con=-con;
	cine.fs=(C1/B1+(con-C)/B)/(A/B-A1/B1);
	cine.sc=-(A1/B1*cine.fs+C1/B1);
      	if(s.find(cine)!=s.end())
		++rez;	
}
int main()
{
	freopen("triang.in","r",stdin);
	freopen("triang.out","w",stdout);
	citire();
	for(int i=0; i<n; ++i)
	{
		for(int j=i+1; j<n; ++j)
		{
			vezi(v[i],v[j]);
		       // printf("%d\n",rez);
		}
	}
	printf("%d\n",rez/3);
	return 0;
}