Cod sursa(job #737519)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 19 aprilie 2012 16:29:53
Problema Patrate 3 Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
#define mod 1001
#define eps 0.000000001
struct punct {
	long double x,y;
};
vector <punct> v[mod];
punct a[1001];
inline bool cmp(const punct &a, const punct &b)
{
	if(fabs(a.y-b.y)<eps)
		return a.x<=b.x;
	return a.y<b.y;
}
inline int compara(punct a, punct b)
{
	if(fabs(a.x-b.x)>eps)
		return 0;
	if(fabs(a.y-b.y)>eps)
		return 0;
	return 1;
}		
inline void adauga(punct x)
{
	int k;
	k=(int)(x.x+x.y)%mod;
	if(k<0)
		k=-k;
	v[k].push_back(x);
}
inline int cauta(punct x)
{
	int n,i,k;
	k=(int)(x.x+x.y)%mod;
	if(k<0)
		k=-k;
	n=v[k].size()-1;
	for(i=0;i<=n;i++) 
		if(compara(v[k][i],x))
			return 1;
	return 0;
}
int main ()
{
	int n,i,j,nr;
	punct x,y;
	long double alfa,d;
	alfa=0;
	d=1.5;
	alfa=alfa+d;
	ifstream f("patrate3.in");
	ofstream g("patrate3.out");
	f>>n;
	for(i=1;i<=n;i++) {
		f>>a[i].x>>a[i].y;
		adauga(a[i]);
	}
	f.close();
	sort(a+1,a+n+1,cmp);
	nr=0;
	for(i=1;i<=n-1;i++)
		for(j=i+1;j<=n;j++) {
			d=(long double)((a[j].x-a[i].x)*(a[j].x-a[i].x)+(a[j].y-a[i].y)*(a[j].y-a[i].y));
			
			x.y=a[j].y-(a[j].x-a[i].x);
			alfa=(long double)sqrt(d-(a[j].y-x.y)*(a[j].y-x.y));
			x.x=a[j].x+alfa;
			y.y=a[i].y-(a[j].x-a[i].x);
			alfa=(long double)sqrt(d-(a[i].y-y.y)*(a[i].y-y.y));
			y.x=a[i].x+alfa;
			
			if((cauta(x))&&(cauta(y)))
				nr++;
			
			x.y=a[j].y+(a[j].x-a[i].x);
			alfa=(long double)sqrt(d-(a[j].y-x.y)*(a[j].y-x.y));
			x.x=a[j].x-alfa;
			y.y=a[i].y+(a[j].x-a[i].x);
			alfa=(long double)sqrt(d-(a[i].y-y.y)*(a[i].y-y.y));
			y.x=a[i].x-alfa;
			
			if((cauta(x))&&(cauta(y)))
				nr++;
		}
	if(nr%4!=0)
		g<<nr/4+1;
	g<<nr/4;
	g.close();
	return 0;
}