Cod sursa(job #210902)

Utilizator mordredSimionescu Andrei mordred Data 29 septembrie 2008 21:47:44
Problema Patrate 3 Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <stdio.h>
#include <algorithm>
#define nmax 1001
using namespace std;

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

void citire();
void output();
bool egal(float a, float b){return (a - b < 0.00001 && b - a < 0.00001);}
//sorteaza crescator dupa x, sau dupa y, cand x[i] = x[j]
int cmp(int i, int j) { return ((a[i].x < a[j].x) || (egal(a[i].x, a[j].x) && a[i].y <= a[j].y)); }
//schimba intre ele punctele x si y
void swap(int i, int j) {punct aux; aux = a[i]; a[i] = a[j]; a[j] = aux;}
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){
        swap(k,i);
        }
    }
swap(start,k);
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);
}