Nu aveti permisiuni pentru a descarca fisierul grader_test3.ok

Cod sursa(job #31104)

Utilizator tm_raduToma Radu tm_radu Data 15 martie 2007 15:17:57
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <stdio.h>
#include <math.h>
#define eps 0.0000001

int n, i, j;
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-2; i++ )
		for ( j = 1; j <= n-1; j++ )
		{
			if ( i == j ) continue;
			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/2);
    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 = ((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));
	l = double(3*l/4);
	if ( fabs(y[i]-y[j]) < eps )
	{
		yc[0] = y[i] + sqrt(l);
		yc[1] = y[i] - sqrt(l);
		if ( fabs(y[i]-sqrt(l)) < eps ) yc[1] = 0;
		xc[0] = xc[1] = (x[i]+x[j])/2;
	}
	else
	{
		k = (x[j]-x[i])/(y[j]-y[i]);
		k = k*k+1;
		if ( fabs(x[i]-x[j]) < eps )
		{
			xc[0] = x[i]-sqrt(l);
			if ( fabs(x[i]-sqrt(l)) < eps ) xc[0] = 0;
			xc[1] = x[i]+sqrt(l);
			yc[0] = yc[1] = (y[i]+y[j])/2;
		}
		else
		{
			k = sqrt(l/k);
			double yo = (y[i]+y[j])/2;
			double xo = (x[i]+x[j])/2;
			xc[0] = xo+k;
			xc[1] = xo-k;
			if ( fabs(xo-k) < eps ) xc[1] = 0;
			yc[0] = k*xc[0]-k*xo-yo;
			yc[1] = k*xc[1]-k*xo-yo;
		}
    }
}