Pagini recente » Cod sursa (job #730375) | Cod sursa (job #1887169) | Cod sursa (job #3152071) | Cod sursa (job #1608676) | Cod sursa (job #1840058)
#include <cstdio>
#include <algorithm>
#define MAXN 120000
using namespace std;
struct POINT{
double x, y;
}v[MAXN + 5];
int top1, top2;
int upper[MAXN + 5], lower[MAXN + 5];
bool cmp(POINT a, POINT b) {
return a.x < b.x || ( a.x == b.x && a.y < b.y );
}
double ccw(POINT a, POINT b, POINT c) {
return a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y;
}
int main(){
FILE *f1, *f2;
int n, i;
f1 = fopen( "infasuratoare.in", "r" );
f2 = fopen( "infasuratoare.out", "w" );
fscanf( f1, "%d", &n );
for( i = 0; i < n; i++ ){
fscanf( f1, "%lf%lf", &v[i].x, &v[i].y );
}
sort( v, v + n, cmp );
top1 = 0;
for( i = 0; i < n; i++ ){
while( top1 >= 2 && ccw( v[i], v[lower[top1 - 1]], v[lower[top1 - 2]] ) > 0 ){
top1--;
}
lower[top1] = i;
top1++;
}
top2 = 0;
for( i = 0; i < n; i++ ){
while( top2 >= 2 && ccw( v[i], v[upper[top2 - 1]], v[upper[top2 - 2]] ) < 0 ){
top2--;
}
upper[top2] = i;
top2++;
}
fprintf( f2, "%d\n", top1 + top2 - 2 );
for( i = 0; i < top1; ++i ) {
fprintf( f2, "%lf %lf\n", v[lower[i]].x, v[lower[i]].y );
}
for( i = top2 - 2; i > 0; --i ) {
fprintf( f2, "%lf %lf\n", v[upper[i]].x, v[upper[i]].y );
}
fclose( f1 );
fclose( f2 );
return 0;
}