Cod sursa(job #737608)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 19 aprilie 2012 19:32:32
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<math.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define mod 1001
struct punct {
	int x,y;
};
vector <punct> v[mod];
punct a[1001];
char c[31];
inline bool cmp(const punct a, const punct b)
{
	if(a.y==b.y)
		return a.x<=b.x;
	return a.y<b.y;
}
	
inline void adauga(punct x)
{
	int k;
	k=(0LL+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=(0LL+x.x+x.y)%mod;
	if(k<0)
		k=-k;
	n=v[k].size()-1;
	for(i=0;i<=n;i++) 
		if((v[k][i].x==x.x)&&(v[k][i].y==x.y))
			return 1;
	return 0;
}
int main ()
{
	int n,i,j,nr,m,p;
	punct x,y;
	long double alfa;
	double d;
	ifstream f("patrate3.in");
	ofstream g("patrate3.out");
	f>>n;
	f.get();
	for(i=1;i<=n;i++) {
		f.get(c,30);
		f.get();
		m=strlen(c)-1;
		j=0;
		if(c[j]=='-') {
			j++;
			p=-1;
		}
		else p=1;
		while(c[j]!=' ') {
			if(c[j]!='.') 
				a[i].x=a[i].x*10+c[j]-48;
			j++;
		}
		a[i].x=a[i].x*p;
		j++;
		if(c[j]=='-') {
			j++;
			p=-1;
		}
		else p=1;
		while(j<=m) {
			if(c[j]!='.') 
				a[i].y=a[i].y*10+c[j]-48;
			j++;
		}
		a[i].y=a[i].y*p;
		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)(1LL*(a[j].x-a[i].x)*(a[j].x-a[i].x)+1LL*(a[j].y-a[i].y)*(a[j].y-a[i].y));
			
			x.y=a[j].y-(a[j].x-a[i].x);
			alfa=(double)sqrt(d-1LL*(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=(double)sqrt(d-1LL*(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=(double)sqrt(d-1LL*(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=(double)sqrt(d-1LL*(a[i].y-y.y)*(a[i].y-y.y));
			y.x=a[i].x-alfa;
			
			if((cauta(x))&&(cauta(y)))
				nr++;
		}
	g<<nr/4;
	g.close();
	return 0;
}