Pagini recente » Cod sursa (job #1699748) | Cod sursa (job #1531840) | Cod sursa (job #982640) | fmi-no-stress-9-warmup | Cod sursa (job #3203006)
#include <bits/stdc++.h>
#define N 120008
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, k;
struct point{
double x, y;
bool operator!=(point A){
return A.x != x || A.y != y;
}
bool operator==(point A){
return A.x == x && A.y == y;
}
} v[N], sol[N];
void Citire()
{
int i;
fin >> n;
for( i=1; i<=n; i++ ){
fin >> v[i].x >> v[i].y;
}
}
int Orientare( point A, point B, point C )
{
if( (C.y - A.y)*(B.x - A.x) - (B.y - A.y)*(C.x - A.x) < 0 )
return -1;
if( (C.y - A.y)*(B.x - A.x) - (B.y - A.y)*(C.x - A.x) > 0 )
return 1;
return 0;
}
double dist( point A, point B ){
return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
}
void Rezolvare()
{
int i;
point P, P0;
double xmn = 2e9;
for( i=1; i<=n; i++ ){
if( v[i].x < xmn ){
xmn = v[i].x;
P = v[i];
}
else if( v[i].x < xmn ) if( v[i].y < P.y ){
P = v[i];
}
}
P0 = P;
while(true){
sol[++k] = P;
point NEXT;
for( i=1; i<=n; i++ )
if( v[i] != P ) {NEXT = v[i]; break;}
for( i=1; i<=n; i++ )
if( v[i] != P && v[i] != NEXT ){
if( Orientare( P, NEXT, v[i] ) < 0 )
NEXT = v[i];
else if( Orientare( P, NEXT, v[i] ) == 0 )
if( dist( P, v[i] ) > dist( P, NEXT ) )
NEXT = v[i];
}
if( NEXT == P0 ) break;
P = NEXT;
}
fout << k << "\n";
fout << fixed << setprecision(12);
for( i=1; i<=k; i++ )
fout << sol[i].x << " " << sol[i].y << "\n";
}
int main()
{
Citire();
Rezolvare();
return 0;
}