Nu aveti permisiuni pentru a descarca fisierul grader_test3.ok
Cod sursa(job #31104)
Utilizator | 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;
}
}
}