Pagini recente » Cod sursa (job #652738) | Cod sursa (job #2289819) | Cod sursa (job #1523846) | Cod sursa (job #206499) | Cod sursa (job #290525)
Cod sursa(job #290525)
#include <fstream>
#include <iomanip>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define trace(x) cerr<<setprecision(18)<<#x<<"="<<x<<"\n"
#define scanf __tmp=(void*)scanf
#define freopen __tmp=(void*)freopen
void* __tmp;
struct point {
double x, y;
point() {}
point( double a, double b ) { x=a, y=b; }
} ref;
bool operator<(point A, point B) {
return A.y<B.y || (A.y==B.y && A.x<B.x);
}
bool test(point A, point B, point C) {
double dx1 = B.x-A.x, dy1 = B.y-A.y;
double dx2 = C.x-B.x, dy2 = C.y-B.y;
return dx1*dy2 > dx2*dy1;
return atan2(dy1,dx1) > atan2(dy2,dx2);
}
bool comp(point A, point B) {
double dx1 = A.x-ref.x, dx2 = B.x-ref.x;
double dy1 = A.y-ref.y, dy2 = B.y-ref.y;
return dx1*dy2 > dx2*dy1;
}
vector<point> A;
void convex( vector<point> &A ) {
int N = A.size(), t=0;
for ( int i=1; i<N; ++i )
t = ( A[i]<A[t] ) ? i : t;
ref = A[t];
// trace(ref.x); trace(ref.y);
swap(A[t], A[0]);
sort(A.begin()+1, A.end(), comp);
vector<point> r;
r.push_back(A[0]);
r.push_back(A[1]);
for ( int i=2; i<N; ++i ) {
while ( r.size() >= 2 ) {
ref = r[r.size()-1];
if ( test(r[r.size()-2], ref, A[i]) ) break;
r.pop_back();
}
r.push_back(A[i]);
}
A = r;
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int N;
scanf("%d", &N);
for ( int i=0; i<N; ++i ) {
double x, y;
scanf("%lf %lf", &x, &y);
A.push_back(point(x, y));
}
convex(A);
printf("%d\n", A.size());
for ( vector<point>::iterator i=A.begin(); i!=A.end(); ++i )
printf("%.6lf %.6lf\n", i->x, i->y);
return 0;
}