Pagini recente » Cod sursa (job #1959792) | Cod sursa (job #2825255) | Cod sursa (job #1919228) | Cod sursa (job #3225699) | Cod sursa (job #290517)
Cod sursa(job #290517)
#include <fstream>
#include <iomanip>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define trace(x) cerr<<setprecision(18)<<#x<<"="<<x<<"\n"
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
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) {
// return comp(A,C);
double dx1 = B.x-A.x, dy1 = B.y-A.y;
double dx2 = C.x-B.x, dy2 = C.y-B.y;
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 atan2(dy1,dx1) > atan2(dy2,dx2);
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() {
int N;
in >> N;
in >> setprecision(9);
for ( int i=0; i<N; ++i ) {
double x, y;
in >> x >> y;
A.push_back(point(x, y));
}
convex(A);
out << A.size() << "\n";
for ( vector<point>::iterator i=A.begin(); i!=A.end(); ++i )
out << setprecision(18) << i->x << " " << i->y << "\n";
return 0;
}