Cod sursa(job #210909)

Utilizator mordredSimionescu Andrei mordred Data 29 septembrie 2008 21:53:56
Problema Patrate 3 Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <stdio.h>
#include <algorithm>
#define cmp(i,j) ((a[i].x < a[j].x) || (egal(a[i].x, a[j].x) && a[i].y <= a[j].y))
#define nmax 1001
using namespace std;

int n;
int i,j,suma;
struct punct{float x,y;}a[nmax],aux;
bool used[nmax][nmax];

void citire();
void output();
bool egal(float a, float b){return (a - b <= 0.00001 && b - a <= 0.00001);}
int cmp2(float z, float t, punct q)
{
    if(egal(z, q.x)&& egal(t, q.y)) return 0;
    else if((z < q.x) || (egal(z,q.x) && t < q.y)) return -1;
    else return 1;
}
//quicksort
void quicksort(int start, int end){
if(end - start < 1) return;
int pivot = start, i = start, k = end;
while(k>i)
    {
    while( cmp(i,pivot) && i<=end && k > i)
        ++i;
    while(!cmp(k,pivot) && k>=start && k>=i)
        --k;
    if(k>i){
        aux=a[k],a[k]=a[i],a[i]=aux;
        }
    }
aux=a[start],a[start]=a[k],a[k]=aux;
quicksort(start,k-1);
quicksort(k+1,end);
}
//cautare binara
int cautareBinara(float x, float y){
 int lo, hi, mid;
 
 for (lo = 0, hi = n-1; lo <= hi; )
    {
    mid = lo + (hi-lo) / 2;
    if (cmp2(x,y,a[mid])<0) hi = mid-1;
    else if (cmp2(x,y,a[mid])>0) lo = mid+1;
    else return mid;
    }
 return 0;
}

int main(){
 citire();
 quicksort(0,n-1);

 int x1,x2;
 for(i=0;i<n-1;++i)
    for(j=i+1;j<n;++j)
        {
        x1 = cautareBinara((a[i].x+a[j].x)/2 - (a[j].y-a[i].y)/2, (a[i].y+a[j].y)/2 + (a[j].x-a[i].x)/2);
        x2 = cautareBinara((a[i].x+a[j].x)/2 + (a[j].y-a[i].y)/2, (a[i].y+a[j].y)/2 - (a[j].x-a[i].x)/2);
        if(x1 && x2 && !used[i][j])
            ++suma,used[x2][x1]=1;
//            printf("%d\n",suma),
//            printf("%d %f %f\n",i,a[i].x,a[i].y),
//            printf("%d %f %f\n",x1,a[x1].x,a[x1].y),
//            printf("%d %f %f\n",j,a[j].x,a[j].y),
//            printf("%d %f %f\n",x2,a[x2].x,a[x2].y);
        }
 output();
 return 0;
}

void citire(){
 freopen("patrate3.in","r",stdin);
 scanf("%d",&n);
 for(i=0;i<n;++i)
    scanf("%f %f",&a[i].x,&a[i].y);
}

void output(){
 freopen("patrate3.out","w",stdout);
 printf("%d\n",suma);
}