Pagini recente » Cod sursa (job #2988887) | Cod sursa (job #707703) | Cod sursa (job #68707) | Cod sursa (job #2559911) | Cod sursa (job #289796)
Cod sursa(job #289796)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX 100100
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct point {
double x, y;
point( double _x, double _y ) { x = _x, y = _y; }
point() {}
};
vector<point> V;
int M, N, i, j;
point ref;
bool operator<( const point& A, const point& B ) {
double Adx = A.x-ref.x, Ady = A.y-ref.y;
double Bdx = B.x-ref.x, Bdy = B.y-ref.y;
return Adx*Bdy > Ady*Bdx;
}
void convex( vector<point> &A ) {
int t=0, i;
for ( i=1; i<N; ++i )
if ( A[i].y < A[t].y || (A[i].y==A[t].y && A[i].x<A[t].x) )
t = i;
ref = A[t];
sort(A.begin(), A.end());
vector<point> r;
r.push_back(A[0]);
r.push_back(A[1]);
r.push_back(A[2]);
for ( i=3; i<N; ++i ) {
while ( r.size()>=2 ) {
ref = r[r.size()-2];
if ( r[r.size()-1] < A[i] )
break;
r.pop_back();
}
r.push_back(A[i]);
}
A = r;
}
int main() {
// load
in >> N;
for ( i=0; i<N; ++i ) {
double x, y;
in >> x >> y;
V.push_back(point(x, y));
}
// magic stuff
convex(V);
// write
out << V.size() << "\n";
for ( i=0; i<V.size(); ++i )
out << V[i].x << " " << V[i].y << "\n";
return 0;
}