Pagini recente » Cod sursa (job #449265) | Cod sursa (job #574460) | Cod sursa (job #1352818) | Cod sursa (job #1423327) | Cod sursa (job #31116)
Cod sursa(job #31116)
#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);
}