Cod sursa(job #11031)

Utilizator rokadaIacob Andrei Vasile rokada Data 30 ianuarie 2007 12:36:26
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include<fstream.h>
#include<math.h>
struct punct
{
 float x,y;
};
punct a[1001];
int i,n,ct=0,mij,st,dr,j,gasit1,gasit2;
float mijx,mijy,dx,dy,x2,x3,y2,y3;
void quick(int p,int q)
{
 int i,j,t;
 float auxx,auxy;
 if(p<q)
 {
  i=p;
  j=q;
  t=1;
  do
  {
   if(a[i].x>a[j].x)
   {
    auxx=a[i].x;
    a[i].x=a[j].x;
    a[j].x=auxx;
    auxy=a[i].y;
    a[i].y=a[j].y;
    a[j].y=auxy;
    t=!t;
   }
   else
   if(a[i].x==a[j].x&&a[i].y>a[j].y)
   {
    auxx=a[i].x;
    a[i].x=a[j].x;
    a[j].x=auxx;
    auxy=a[i].y;
    a[i].y=a[j].y;
    a[j].y=auxy;
    t=!t;
   }
   if(t)
   j--;
   else
   i++;
  }while(i!=j);
  quick(p,i-1);
  quick(i+1,q);
 }
}
int main()
{
 ifstream f("patrate3.in");
 ofstream g("patrate3.out");
 f>>n;
 for(i=1;i<=n;i++)
  f>>a[i].x>>a[i].y;
  quick(1,n);
  for(i=1;i<n;i++)
   for(j=i+1;j<=n;j++)
    {
     mijx=(a[i].x+a[j].x)/2;
     mijy=(a[i].y+a[j].y)/2;
      dx=abs(mijx-a[i].x);
      dy=abs(mijy-a[i].y);
      if(a[i].y<a[j].y)
       {
        x2=mijx+dy;
        y2=mijy-dx;
        x3=mijx-dy;
        y3=mijy+dx;
       }
       else
       {
        x2=mijx-dy;
        y2=mijy-dx;
        x3=mijx+dy;
        y3=mijy+dx;
        }
        gasit1=1;
        st=1;
        dr=n;
        while(gasit1&&st<dr)
         {
          mij=(st+dr)/2;
           if(a[mij].x==x2&&a[mij].y==y2)
            gasit1=0;
            else
            if(a[mij].x<=x2)
             st=mij+1;
            else
             dr=mij-1;
          }
          if(gasit1==0)
          {
        gasit2=1;
        st=1;
        dr=n;
        while(gasit2&&st<dr)
         {
          mij=(st+dr)/2;
           if(a[mij].x==x3&&a[mij].y==y3)
            gasit2=0;
            else
            if(a[mij].x>=x3)
             st=mij+1;
            else
             dr=mij-1;
          }
          }
          if(gasit1==0&&gasit2==0)
            ct++;
       }
       g<<ct;
 //for(i=1;i<=n;i++)
  //g<<a[i].x<<" "<<a[i].y<<'\n';
  return 0;
 }