Cod sursa(job #31116)

Utilizator tm_raduToma Radu tm_radu Data 15 martie 2007 15:44:57
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <stdio.h>
#include <math.h>
#define eps 0.00001

int n;
double x[1001], y[1001];
double xv, yv;
int i, j, k;
int o1, o2;
int nrsol;

int Cbin(int st, int dr);
int Egal(int g);
void Qsort(int st, int dr);

int main()
{
    freopen("patrate3.in", "r", stdin);
	freopen("patrate3.out", "w", stdout);
	scanf("%d", &n);
	for ( i = 1; i <= n; i++ )
		scanf("%lf %lf", &x[i], &y[i]);
	Qsort(1, n);
    for ( i = 1; i <= n; i++ )
        for ( j = 1; j <= n; j++ )
            if ( i != j )
            {
                o1 = o2 = 0;
                xv = y[i]-y[j]+x[i];
                yv = x[i]-x[j]+y[i];
                o1 = Cbin(1, n);
                xv = y[i]-y[j]+x[j];
                yv = x[i]-x[j]+y[j];
                o2 = Cbin(1, n);
                if ( o1 && o2 ) nrsol++;
                o1 = o2 = 0;
                xv = x[i]-y[i]+y[j];
                yv = x[i]-x[j]+y[i];
                o1 = Cbin(1, n);
                xv = x[j] - y[i]+y[j];
                yv = x[i]-x[j]+y[j];
                o2 = Cbin(1, n);
                if ( o1 && o2 ) nrsol++;
            }    
    printf("%d\n", nrsol\4);
    return 0;
}		
	
void Qsort(int st, int dr)
{
    int i = st-1;
    int j = dr+1;
    do
    {
    	do { i++; } while ( x[i] < x[st] || (fabs(x[i]-x[st]) < eps && y[i] < y[st]) );
	    do { j--; } while ( x[st] < x[j] || (fabs(x[st]-x[j]) < eps && y[st] < y[j]) );
        if ( i <= j )
        {
            double aux = x[i];
            x[i] = x[j];
            x[j] = aux;
            aux = y[i];
            y[i] = y[j];
            y[j] = aux;
        }
    } while ( i <= j );
    if ( st < j ) Qsort(st, j);
    if ( i < dr ) Qsort(i, dr);
}

int Egal(int g)
{
    if ( fabs(xv-x[g]) < eps )
    {
    	if ( fabs(yv-y[g]) < eps ) return 0;
	    if ( yv < y[g] ) return -1;
    	if ( yv > y[g] ) return 1;
    }
    if ( xv < x[g] ) return -1;
    if ( xv > x[g] ) return 1;
    return 2;
}

int Cbin(int st, int dr)
{
    if ( st == dr )        
	    if ( Egal(st) == 0) return 1;
	    else                return 0;
    if ( st == dr-1 )
    {
	    if ( Egal(st) == 0 ) return 1;
    	if ( Egal(dr) == 0 ) return 1;
	    return 0;
    }
    int mij = (st+dr)/2;
    int v = Egal(mij);
    if ( v == 0 ) return 1;
    if ( v < 0 ) return Cbin(st, mij-1);
    return Cbin(mij+1, dr);
}