Pagini recente » Cod sursa (job #1205479) | Cod sursa (job #2478660) | Cod sursa (job #826449) | Cod sursa (job #223146) | Cod sursa (job #255279)
Cod sursa(job #255279)
#include <cstdio>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
#ifdef __ACASA__
#define MAX 100
#else
#define MAX 124000
#endif
struct point { double x, y; } A[MAX], mi;
int N, i, S[MAX], k;
int comp( point A, point B ) {
return atan2(A.y-mi.y,A.x-mi.x) < atan2(B.y-mi.y,B.x-mi.x);
}
int can_pop( int lvl, int i ) {
point P, Q;
P.x = A[i].x - A[S[lvl]].x;
P.y = A[i].y - A[S[lvl]].y;
Q.x = A[S[lvl]].x - A[S[lvl-1]].x;
Q.y = A[S[lvl]].y - A[S[lvl-1]].y;
double delta = Q.x * P.y - Q.y * P.x;
return delta < 0;
}
int main() {
// load
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
// scanf( "%d", &N );
in >> N;
for ( i=0; i<N; ++i ) {
// scanf( "%lf %lf", &A[i].x, &A[i].y );
in >> A[i].x >> A[i].y;
mi = i==0 ? A[i] : ( mi.y > A[i].y || (mi.y==A[i].y && mi.x > A[i].x) ? A[i] : mi );
}
sort( A, A+N, comp );
// solve
S[0] = 0, S[1] = 1, k = 2;
for ( i=2; i<N; ++i ) {
while ( k>1 && can_pop(k-1,i) ) --k;
S[ k++ ] = i;
}
out << k << "\n";
// printf( "%d\n", k );
for ( i=0; i<k; ++i ) {
// printf( "%lf %lf\n", A[S[i]].x, A[S[i]].y );
out << A[S[i]].x << " " << A[S[i]].y << "\n";
}
in.close(); out.close();
return 0;
}