Pagini recente » Cod sursa (job #1094447) | Cod sursa (job #949071) | Cod sursa (job #2045851) | Cod sursa (job #1354511) | Cod sursa (job #928324)
Cod sursa(job #928324)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 120005
#define eps 0.000000000001
#define infinit 1000000000
struct punct
{
double x, y ;
};
int n ;
punct v[maxn] ;
double xs = infinit, ys = infinit ;
int inf[maxn] ;
int sign ;
bool sel[maxn] ;
int comp(double a, double b)
{
if( a - b < eps && a - b > -eps )
return 0 ;
if( a - b < -eps )
return -1 ;
return 1 ;
}
void citire()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i )
{
scanf("%lf%lf", &v[i].x, &v[i].y);
if( comp( v[i].x, xs ) == -1 )
{
xs = v[i].x ;
ys = v[i].y ;
inf[1] = i ;
}
if( comp( v[i].x, xs ) == 0 && comp( v[i].y, ys ) == -1 )
{
xs = v[i].x ;
ys = v[i].y ;
inf[1] = i ;
}
}
}
int semn(double A, double B, double C, int indp)
{
double XX = v[indp].x ;
double YX = v[indp].y ;
double expr = A * XX + B * YX + C ;
return comp( expr, 0 ) ;
}
bool verifica(int ind1, int ind2)
{
bool ok = true ;
double XA = v[ind1].x ;
double YA = v[ind1].y ;
double XB = v[ind2].x ;
double YB = v[ind2].y ;
double A = YB - YA ;
double B = XA - XB ;
double C = XB * YA - XA * YB ;
for(int i = 1; i <= n; ++i )
{
if( i == ind1 || i == ind2)
continue;
if( semn( A, B, C, i ) > 0 )
{
ok = false ;
break ;
}
}
return ok ;
}
int rezolvare()
{
bool ok = true ;
int ind = 1 ;
sel[ inf[1] ] = true ;
while( ok )
{
ok = false ;
for(int i = 1; i <= n; ++i )
{
if( sel[i] == false && verifica( inf[ind], i ) == true )
{
++ind ;
inf[ind] = i ;
sel[i] = true ;
ok = true ;
break ;
}
}
}
return ind;
}
void afisare(int ind)
{
printf("%d\n", ind);
for(int i = 1; i <= ind; ++i )
printf("%.6lf %.6lf\n", v[ inf[i] ].x, v[ inf[i] ].y );
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
citire() ;
afisare(rezolvare() ) ;
return 0 ;
}