Pagini recente » Cod sursa (job #725096) | Cod sursa (job #1633454) | Cod sursa (job #838123) | Cod sursa (job #562255) | Cod sursa (job #1963288)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
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));
}
pair<double, double> around;
bool cmp(pair<double, double> a, pair<double, double> b) {
return cross_product(around, a, b) < 0;
}
pair<double, double> points[120003];
pair<int, int> st[120003];
int am;
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].first < points[F].first) {
F = i;
} else if(points[i].first == points[F].first) {
if(points[i].second < points[F].second)
F = i;
}
}
swap(points[1], points[F]);
around = 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 = 1; i <= am; i++) {
out << st[i].first << " " << st[i].second << '\n';
}
return 0;
}