Cod sursa(job #644823)

Utilizator lianaliana tucar liana Data 7 decembrie 2011 18:26:00
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define pi 3.14159
#define nmax 1600
#define prec 0.001
struct punct{double x, y;};
long i, n, st, dr, m, rez, j;
punct v[nmax];
double difx, dify, x, y, l;

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)));}

void cautare()
{
	st=j+1;	dr=n;
	while (st<=dr)
	{
		m=(st+dr)/2;
		difx=v[m].x-x;	dify=v[m].y-y;
		if (difx<0)
			difx=-difx;
		if (dify<0)
			dify=-dify;
		if ((v[m].x>x)||((difx<=prec)&&(dify<=prec)))
			dr=m-1;
		else
			st=m+1;
	}
	difx=v[st].x-x;	dify=v[st].y-y;
	if (difx<0)
		difx=-difx;
	if (dify<0)
			dify=-dify;
	rez+=((difx<=prec)&&(dify<=prec)&&(st<=n));
}

void rezolvare()
{
	for (i=1;i<=n;i++)
		for (j=i+1;j<=n;j++)
		{
			l=pi/3;
			x=(v[j].x-v[i].x)*cos(l)-(v[j].y-v[i].y)*sin(l) + v[i].x;
			y=(v[j].x-v[i].x)*sin(l)+(v[j].y-v[i].y)*cos(l) + v[i].y;
			cautare();
			l=-(pi/3);
			x=(v[j].x-v[i].x)*cos(l)-(v[j].y-v[i].y)*sin(l) + v[i].x;
			y=(v[j].x-v[i].x)*sin(l)+(v[j].y-v[i].y)*cos(l) + 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;
}