Cod sursa(job #31052)

Utilizator tm_raduToma Radu tm_radu Data 15 martie 2007 14:01:34
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <stdio.h>
#include <math.h>
#define eps 0.001

int n, i, j, h;
double x[1501], y[1501];
int nrsol;
double k;
double xv, yv;
double xc[2], yc[2];

int Cbin(int st, int dr);
void Coord(int i, int j);
int Egal(int k);
void Qsort(int st, int dr);
 
int main()
{
    freopen("triang.in", "r", stdin);
    freopen("triang.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 = i+1; j <= n; j++ )
        {
            Coord(i, j);
            xv = xc[0], yv = yc[0];
	    if ( Cbin(1, n) )
		nrsol++;
	    xv = xc[1], yv = yc[1];
	    if ( Cbin(1, n) )
                nrsol++;
        }
    printf("%d\n", nrsol);
    return 0;
}

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);
}

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 h)
{
    if ( fabs(xv-x[h]) < eps )
    {
	if ( fabs(yv-y[h]) < eps ) return 0;
	if ( yv < y[h] ) return -1;
	if ( yv > y[h] ) return 1;
    }
    if ( xv < x[h] ) return -1;
    if ( xv > x[h] ) return 1;
    return 2;
}

void Coord(int i, int j)        
{
    double l = sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));
    l = double(sqrt(3)*l/2);
    if ( fabs(y[i]-y[j]) < eps ) 
    {
        yc[0] = y[i] + l;
        yc[1] = y[i] - l;
        xc[0] = xc[1] = (x[i]+x[j])/2;
    }
    else
    {
        k = (x[j]-x[i])/(y[j]-y[i]);
        k = k*k+1;
        k = sqrt(l/k);
        double yo = (y[i]+y[j])/2;
        double xo = (x[i]+x[j])/2;
        yc[0] = yo+k;
        yc[1] = yo-k;
        xc[0] = k*yc[0]-k*yo-xo;
        xc[1] = k*yc[1]-k*yo-xo;
    }
}