Cod sursa(job #644893)

Utilizator lianaliana tucar liana Data 7 decembrie 2011 19:36:02
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
#define pi 3.14159
#define nmax 1600
#define cos 0.5
#define sin 0.866
struct punct{double x, y;};
long i, n, st, dr, m, rez, j;
punct v[nmax];
double x, y, l, prec=1.0e-3, dif;

void citire()
{
	scanf("%ld",&n);
	for (i=1;i<=n;i++)
		scanf("%lf %lf",&v[i].x,&v[i].y);
}

bool cmp(punct a, punct b)
{	return ((a.x<b.x)||((a.x==b.x)&&(a.y<b.y)));}

bool egal(double a, double b)
{
	dif=a-b;
	if (dif<0)
		dif=-dif;
	return dif<prec;
}

bool mmare(double a, double b)
{
	if (a-b>prec)
		return 1;
	return 0;
}

void cautare()
{
	st=j+1;	dr=n;
	while (st<=dr)
	{
		m=(st+dr)/2;
		if ( mmare(v[m].x,x) || (egal(v[m].x,x)&&mmare(v[m].y,y)) || (egal(v[m].x,x)&&egal(v[m].y,y)) )
			dr=m-1;
		else
			st=m+1;
	}
	if (egal(v[st].x,x)&&egal(v[st].y,y)&&(st<=n))
		rez++;
}

void rezolvare()
{
	for (i=1;i<=n;i++)
		for (j=i+1;j<=n;j++)
		{
			x=(v[j].x-v[i].x)*cos - (v[j].y-v[i].y)*sin + v[i].x;
			y=(v[j].x-v[i].x)*sin + (v[j].y-v[i].y)*cos + v[i].y;
			cautare();
			x=(v[j].x-v[i].x)*cos + (v[j].y-v[i].y)*sin + v[i].x;
			y=-(v[j].x-v[i].x)*sin + (v[j].y-v[i].y)*cos + v[i].y;
			cautare();
		}
}

int main()
{
	freopen("triang.in","r",stdin);
	freopen("triang.out","w",stdout);
	citire();
	sort(v+1,v+1+n,cmp);
	rezolvare();
	printf("%ld",rez);
	return 0;
}