Cod sursa(job #529710)

Utilizator nautilusCohal Alexandru nautilus Data 5 februarie 2011 19:26:19
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include<fstream>
#include<cmath>
#define dmax 1010
#define eps 1e-6
using namespace std;

typedef struct punct
{
 long double x,y;
} punct;

punct p[dmax];
int n;
long double xc,yc;
int gasit;
long long numar;


void citire()
{
 int i;
 long double x,y;
	
 ifstream fin("patrate3.in");
 
 fin>>n;
 for (i=1; i<=n; i++)
	 {	
	  fin>>x>>y;
	  p[i].x = x;
	  p[i].y = y;
	 }
	
 fin.close();
}


bool comp(punct a, punct b)
{
 if (a.x != b.x)
	 return a.x < b.x; else
	 return a.y < b.y;
}


void cauta (int st, int dr)
{
 int mijl = (st + dr) / 2;
	
 if (st <= dr)
	 if (fabs(p[mijl].x - xc) <= eps && fabs(p[mijl].y - yc) <= eps)
		 gasit = 1; else
		 if ((p[mijl].x - xc) > eps || (fabs(p[mijl].x - xc) <= eps && (p[mijl].y - yc) > eps))
			 cauta(st, mijl-1); else
			 cauta(mijl+1, dr);
}


void solve()
{
 int i,j;
 long double xm,ym,dx,dy;
 long double x3,y3,x4,y4;
 int ok1,ok2;
	
 for (i=1; i<=n-1; i++)
	 for (j=i+1; j<=n; j++)
		 {
		  xm = (p[i].x + p[j].x) / 2; ym = (p[i].y + p[j].y) / 2;
		  dx = fabs(xm - p[i].x); dy = fabs(ym - p[i].y);
		  
		  if (p[i].y < p[j].y && p[i].x < p[j].x)
			  {
			   x3 = xm + dx; y3 = ym - dy;
			   x4 = xm - dx; y4 = ym + dy;
			  } else
			  {
			   x3 = xm - dy; y3 = ym - dx;
			   x4 = xm + dy; y4 = ym + dx;
			  }
			  
		   gasit = 0;
		   xc = x3; yc = y3;
		   cauta(1,n);
		   ok1 = gasit;
		   
		   gasit = 0;
		   xc = x4; yc = y4;
		   cauta(1,n);
		   ok2 = gasit;
		  
		  if (ok1 && ok2)
			  numar++;
		 }
}


void afisare()
{
 ofstream fout("patrate3.out");
 
 fout<<numar;
 
 fout.close();
}

int main()
{
	
 citire();
 sort(p+1, p+n+1, comp);
 solve();
 afisare();
	
 return 0;
}