Pagini recente » Cod sursa (job #344014) | Cod sursa (job #559257) | Cod sursa (job #910373) | Cod sursa (job #674647) | Cod sursa (job #1393610)
// How about a coding trick?
#include <cstdio>
#include <algorithm>
#define DIM 120120
using namespace std;
FILE *fin=freopen("infasuratoare.in","r",stdin);
FILE *fout=freopen("infasuratoare.out","w",stdout);
struct Point{
double x, y;
};
Point P[DIM], Stack[DIM];
int cnt;
int n;
double produs(Point P1, Point P2, Point P3)
{
return ( P2.x - P1.x ) * ( P3.y - P1.y ) - ( P3.x - P1.x ) * ( P2.y - P1.y );
}
void Read()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%lf%lf", &P[i].x, &P[i].y);
}
void Find_Min()
{
int k = 1;
for(int i = 2; i <= n; ++i)
if( P[i].y < P[k].y || (P[i].y == P[k].y && P[i].x < P[k].x) )
k = i;
swap(P[1], P[k]);
}
inline bool comp(Point a, Point b)
{
return produs(P[1], a, b) > 0 ;
}
void Solve()
{
Find_Min();
sort(P + 2, P + n + 1, comp);
Stack[1] = P[1], Stack[2] = P[2], cnt = 2;
double val;
for(int i = 3; i <= n; ++i)
{
val = produs(Stack[cnt - 1], Stack[cnt], P[i]);
if( val == 0 )
Stack[cnt] = P[i];
else
{
if( val < 0 )
while( val <= 0 && cnt >= 2 )
{
--cnt;
val = produs(Stack[cnt - 1], Stack[cnt], P[i]);
}
++cnt, Stack[cnt] = P[i];
}
}
printf("%d\n", cnt);
for(int i = 1; i <= cnt; ++i)
printf("%.6f %.6f\n", Stack[i].x, Stack[i].y);
}
int main()
{
Read();
Solve();
return 0;
}