Cod sursa(job #525689)

Utilizator iulishorIulian Popescu iulishor Data 25 ianuarie 2011 21:59:36
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<fstream>
#include<algorithm>
#include<math.h>
using namespace std;
int n,i,j,nr,t,k;
struct point
{
	double x,y;
}; point a[1501];
double x1,y2;
int cmp(const point &a, const point &b)
{
    return a.x < b.x;
}
int caut_binarx(int x)
{
	int st=0,dr=n,ok=0,m;
	do
	{
		m=(st+dr)/2;
		if(a[m].x==x)
		{
			ok=1;
			return m;
		}
		else
			if(a[m].x<x)
				st=m+1;
			else
				dr=m-1;
	}while(st<=dr && !ok);
	if(st>dr)
		return 0;
}
int main()
{
	ifstream f("triang.in");
	ofstream g("triang.out");
	f>>n;
	for(i=1;i<=n;i++)
		f>>a[i].x>>a[i].y;
	sort(a+1,a+n+1,cmp);
	nr=0;
	for(i=1;i<n;i++)
		for(j=i+1;j<=n;j++)
		{
			x1=(a[i].x+a[j].x)/2-1.7320508*(a[j].y-a[i].y)/2;
			y2=(a[j].x-a[i].x)/2*1.7320508+(a[j].y+a[i].y)/2;
			t=caut_binarx(x1);
			if(a[t].y==y2)
				nr++;
			else
			{
				k=t;
				t--;
				k++;
				while(a[t].x==x1)
				{
					if(a[t].y==y2)
					{
						nr++;
						break;
					}
					t--;
				}
				while(a[k].x==x1)
				{
					if(a[k].y==y2)
					{
						nr++;
						break;
					}
					k++;
				}
			}
		}
	g<<nr;
}