Pagini recente » Cod sursa (job #1911146) | Cod sursa (job #511616) | Cod sursa (job #2147526) | Cod sursa (job #703785) | Cod sursa (job #1963435)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
pair<double, double> points[120003];
pair<double, double> st[120003];
int am;
double cross_product(pair<double, double> around, pair<double, double> a, pair<double, double> b) {
return ((a.first-around.first)*(b.second-around.second)) - ((b.first-around.first)*(a.second-around.second));
}
bool cmp(pair<double, double> a, pair<double, double> b) {
return cross_product(points[1], a, b) < 0;
}
int main() {
int n;
in >> n;
int F = 1;
for(int i = 1; i <= n; i++) {
in >> points[i].first >> points[i].second;
if(points[i] < points[F])
F = i;
}
swap(points[1], points[F]);
sort(points+2, points+n+1, cmp);
st[1] = points[1];
st[2] = points[2];
am = 2;
for(int i = 3; i <= n; i++) {
while(am >= 2 && (cross_product(st[am-1], st[am], points[i]) > 0))
am--;
st[++am] = points[i];
}
out << am << '\n';
for(int i = am; i >= 1; i--) {
out << st[i].first << " " << st[i].second << '\n';
}
return 0;
}