Pagini recente » Cod sursa (job #840439) | Cod sursa (job #92564) | Cod sursa (job #2746831) | Cod sursa (job #2413814) | Cod sursa (job #928464)
Cod sursa(job #928464)
#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 rezolvare()
{
int ind = 1 ;
printf("%d\n", inf[1]);
sel[ inf[1] ] = true ;
for(int i = 2; ind == i-1 && i <= n; ++i )
{
if( i == 3)
sel[inf[1]] = false;
int last = inf[i-1];
int next ;
for(int j = 1; j <= n; ++j )
if( sel[j] == false )
{
next = j;
break;
}
for( int j = next + 1; j <= n; ++j)
{
if( j != last )
{
double A = v[next].y - v[last].y ;
double B = v[last].x - v[next].x ;
double C = v[next].x * v[last].y - v[last].x * v[next].y ;
double expr = A * v[j].x + B * v[j].y + C ;
if( comp( expr, 0 ) == 1 )
next = j;
}
}
printf("%d\n", next);
++ind ;
inf[ind] = next ;
sel[next] = true ;
if( next == inf[1])
break;
}
return ind - 1;
}
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 ;
}