Pagini recente » Cod sursa (job #2157163) | Cod sursa (job #1568096) | Cod sursa (job #2176303) | Cod sursa (job #2974201) | Cod sursa (job #937345)
Cod sursa(job #937345)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<double,double> dd;
#define x first
#define y second
#define let(X, A) typeof(A) X(A)
#define ech(It, A) for (let( It, A.begin() ); It != A.end(); ++It)
bool ccw( dd a, dd b, dd c ) { // if collinear return false
return (c.x-b.x) * (b.y-a.y) < (c.y-b.y) * (b.x-a.x);
}
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
fin >> n;
vector<dd> P(n);
for (int i=0; i<n; ++i) {
fin >> P[i].first >> P[i].second;
}
sort( P.begin(), P.end() );
vector<dd> hull(n);
int cnt = 0;
for (int i=0; i<n; ++i) {
while (cnt > 1 && !ccw( hull[cnt-2], hull[cnt-1], P[i] ))
--cnt;
hull[cnt++] = P[i];
}
int dcnt = cnt;
for (int i=n-2; i>=0; --i) {
while (cnt > dcnt && !ccw( hull[cnt-2], hull[cnt-1], P[i] ))
--cnt;
hull[cnt++] = P[i];
}
hull.resize(--cnt);
fout << hull.size() << '\n';
fout.precision(6);
ech( it, hull ) {
fout << fixed << it->x << ' ' << it->y << '\n';
}
return 0;
}