Cod sursa(job #520356)

Utilizator andunhillMacarescu Sebastian andunhill Data 8 ianuarie 2011 10:17:31
Problema Patrate 3 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<fstream>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;
#define eps 0.0000001
ifstream f("patrate3.in");
ofstream g("patrate3.out");
int N,nrt;
struct point 
{	double x,y; 
	bool operator ==(point b)
	{	if(fabs(b.x-x)<eps && fabs(b.y-y)<eps) return 1;
		return 0;
	}
}a[1001];
bool les(double a,double b)
{	if(b-a>=eps) return 1;
	return 0;
}
bool eql(double a,double b)
{	if(fabs(b-a)<eps) return 1;
	return 0;
}
bool cmp(point a,point b)
{	if(a.x<b.x) return 1;
	if(a.x==b.x && a.y<b.y) return 1;
	return 0;
}
bool bin_search(point s)
{	int left,right,mid;
	left=1 , right=N;
	while(left<=right)
	{	mid=(left+right)>>1;
		if(a[mid]==s) return 1;
		if(les(s.x,a[mid].x)) right=mid-1;
		else if(eql(s.x,a[mid].x) && les(s.y,a[mid].y)) right=mid-1;
		if(les(a[mid].x,s.x)) left=mid+1;
		else if(eql(s.x,a[mid].x) && les(a[mid].y,s.y)) left=mid+1;
	}
	return 0;
}
int main()
{	int i,j;
	point b,d,mid;
	f>>N;
	for(i=1;i<=N;i++)
	{	f>>a[i].x>>a[i].y;
	}
	sort(a+1,a+N+1,cmp);
	for(i=1;i<=N;i++)
		for(j=i+1;j<=N;j++)
		{	cout<<fixed<<setprecision(5)<<a[i].x<<" "<<a[i].y<<'\n';
			cout<<fixed<<setprecision(5)<<a[j].x<<" "<<a[j].y<<'\n';
			mid.x=(a[i].x+a[j].x)/2 , mid.y=(a[i].y+a[j].y)/2;
			d.x=a[i].y-a[j].y+a[i].x;
			d.y=a[j].x-a[i].x+a[i].y;
			cout<<fixed<<setprecision(5)<<d.x<<" "<<d.y<<'\n';
			if(!bin_search(d)) continue;
			b.x=a[i].y-a[j].y+a[j].x;
			b.y=a[j].x-a[i].x+a[j].y;
			cout<<fixed<<setprecision(5)<<b.x<<" "<<b.y<<'\n';
			if(!bin_search(b)) continue;
			nrt++;
		}
	g<<nrt/2;
	f.close();
	g.close();
	return 0;
}