Cod sursa(job #457689)

Utilizator siminescuPaval Cristi Onisim siminescu Data 20 mai 2010 22:16:29
Problema Triang Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<fstream>
#include<math.h>
#include<iomanip>
using namespace std;
ifstream f("triang.in");
ofstream g("triang.out");
struct structura{double x,y;};
structura p[1502];
int n;
void citire()
{
	f>>n;int i;
	for(i=0;i<n;i++) f>>p[i].x>>p[i].y;
}
void sortare()
{
	int i,j;
	double aux;
	for(i=0;i<n-1;i++)
		for(j=i+1;j<n;j++)
		{
			if(p[i].x>p[j].x||(p[i].x==p[j].x&&p[i].y>p[j].y))
			{
				aux=p[i].x;
				p[i].x=p[j].x;
				p[j].x=aux;
				aux=p[i].y;
				p[i].y=p[j].y;
				p[j].y=aux;
			}
		}
}
double absolut(double a)
{
	if(a<0) return -a;
	return a;
}
int search(double a,double b,int st)
{
	int dr=n-1,mij;
	do{
		mij=(st+dr)/2;
		if(absolut(p[mij].x-a)<0.001&&absolut(p[mij].y-b)<0.001)
			return 1;
		if(p[mij].x>a||(absolut(p[mij].x-a)<0.001&&p[mij].y>b)) dr=mij;
		else st=mij+1;
	}while(st<dr);
		return 0;
}
int main()
{
	citire();sortare();
	double t,q,a,b,rad3=1.7320508075688772935;int i,j,nr=0;
	for(i=0;i<n-2;i++)
		for(j=1+i;j<n-1;j++)
		{
			a=p[i].x-p[j].x;b=p[i].y-p[j].y;
			t=(a-b*rad3)/2;q=(a*rad3+b)/2;
			nr+=search(t+p[j].x,q+p[j].y,j+1);
			t=(a+b*rad3)/2;q=(b-a*rad3)/2;
			nr+=search(t+p[j].x,q+p[j].y,j+1);
		}
	g<<nr;
}