Cod sursa(job #305418)

Utilizator FlorianFlorian Marcu Florian Data 17 aprilie 2009 11:15:47
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Problemiada - Editia 3 Marime 1.72 kb
#include<cstdio>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define MAX_N 1024
#define EPS 0.0001
struct Punct
{
	float x,y;
};
Punct A[MAX_N];
int N;
inline bool cmp(const Punct &a, const Punct &b)
{
	if(a.x + EPS < b.x) return 1;
	if(b.x + EPS < a.x) return 0;
	if(a.y + EPS < b.y) return 1;
	if(b.y + EPS < a.y) return 0;
	return 0;	
	//return (a.x == b.x) ? (a.y < b.y) : (a.x < b.x);
}
inline int comp(float x, float y) // 1 daca x < y
{
	if( x + EPS < y) return 1;
	if( y + EPS < x) return -1;
	return 0;
}
void read()
{
	freopen("patrate3.in","r",stdin);
	freopen("patrate3.out","w",stdout);
	int i;
	scanf("%d",&N);
	for(i=1;i<=N;++i)
		scanf("%f%f",&A[i].x,&A[i].y);
	sort(A+1,A+N+1,cmp);
}
inline bool binara(Punct F, int i, int j)
{
	int m;
	while(i<=j)
	{
		m = (i+j)/2;
		if( !comp(A[m].x,F.x) && !comp(A[m].y,F.y) ) return 1;
		else if( !comp(A[m].x, F.x) )
		{
			if(comp(A[m].y , F.y) == 1) i = m + 1;
			else j = m - 1;
		}
		else if( comp(A[m].x , F.x) == 1) i = m+1;
		else j = m - 1;
	}
	return 0;
}
void solve()
{
	float xm,ym,dx,dy,yb,yc,xb,xc;
	Punct P,Q;
	int i,j, sol = 0;
	for(i=1;i<=N;++i)
		for(j=i+1;j<=N;++j)
		{
			xm = ( A[i].x + A[j].x) / 2; ym = (A[i].y + A[j].y) / 2;
			dx = xm - A[i].x; dy = ym-A[i].y;
			if(comp(dx,0)==1) dx = (-1)*dx; if(comp(dy,0)==1) dy = (-1)*dy;
			if(A[i].y < A[j].y)
			{
				xb = xm + dy; yb = ym - dx;
				xc = xm - dy; yc = ym + dx;
			}
			else
			{
				xb = xm - dy; yb = ym - dx;
				xc = xm + dy; yc = ym + dx;
			}
			P.x = xb; P.y = yb;
			Q.x = xc; Q.y = yc;
			if(binara(P,i+1,N) && binara(Q,i+1,N)) ++sol;
		}
	printf("%d\n",sol);
}
int main()
{
	read();
	solve();
	return 0;
}