Cod sursa(job #7527)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 21 ianuarie 2007 16:48:54
Problema Patrate 3 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

#define maxn 1010
#define eps 0.00000001
#define db double
#define maxv 1000000000

db a[maxn],b[maxn];
int n,sol,poz[maxn];

db dist(db x1,db x2,db y1,db y2)
{
     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

db tg(db x1,db x2,db y1,db y2)
{
     if (x1==x2) return maxv;
     return (y1-y2)/(x1-x2);
}

int cmp(int x,int y)
{
    if ((a[x]<a[y]) || ((a[x]==a[y]) && (b[x]<b[y]))) return 1;
    return 0;
}

int find(db x,db y)
{
    int front=1,middle,back=n,aux;
    
    while (front<=back)
    {
         middle=(front+back)/2;
         
         if ((fabs(a[poz[middle]]-x)<eps) && (fabs(b[poz[middle]]-y)<eps)) return 1;
         
         if ((a[poz[middle]]>x) || ((a[poz[middle]]==x) && (b[poz[middle]]>=y))) back=middle-1;
         else front=middle+1;
    }
    
    return 0;
}

int main()
{
    freopen("patrate3.in","r",stdin);
    freopen("patrate3.out","w",stdout);
    
    int i,j;
    db p,q,x1,y1,a1,b1,c1,sx1,sx2,sy1,sy2,d;
    scanf("%d ",&n);
    
    for (i=1;i<=n;i++) 
    {
        scanf("%lf %lf",&a[i],&b[i]);
        poz[i]=i;
    }
    
	sort(poz+1,poz+n+1,cmp);
        
    for (i=1;i<=n;i++) 
      for (j=i+1;j<=n;j++) 
      {
          d=dist(a[i],a[j],b[i],b[j]);
		  d=d/2;
          p=tg(a[i],a[j],b[i],b[j]);
          
          if (p==0) p=maxv;
          else p=-1/p;
          
          x1=(a[i]+a[j])/2;
          y1=(b[i]+b[j])/2;
          q=y1-p*x1;
          
          a1=p*p+1;
          b1=2*p*q-2*x1-2*y1*p;
          c1=x1*x1+y1*y1-2*y1*q+q*q-d*d;
          
          sx1=(-b1+sqrt(b1*b1-4*a1*c1))/(2*a1);
          sy1=p*sx1+q;
          
          sx2=(-b1-sqrt(b1*b1-4*a1*c1))/(2*a1);
          sy2=p*sx2+q;
          
          if ((find(sx1,sy1)) && (find(sx2,sy2))) sol++;
      }
      
	printf("%d\n",sol/2);
    
    return 0;
}