Pagini recente » Cod sursa (job #183260) | Cod sursa (job #1334592) | Cod sursa (job #1826719) | Cod sursa (job #536732) | Cod sursa (job #2201479)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
#define NMAX 120005
#define pd pair<double, double>
pd v[NMAX];
pd st[NMAX];
double sinABC(pd A, pd B, pd C) {
return ((C.second - B.second) * (A.first - B.first) -
(C.first - B.first) * (A.second - B.second));
}
bool cmp(pd a, pd b) {
return (sinABC(v[1], a, b) < 0);
}
int main() {
int i, n;
f >> n;
for (i = 1; i <= n; ++i)
f >> v[i].first >> v[i].second;
int pos;
pd maxi = v[1];
for (i = 2; i <= n; ++i)
if (v[i] < maxi) {
maxi = v[i];
pos = i;
}
swap(v[1], v[pos]);
sort(v + 1, v + n + 1, cmp);
int len = 2;
st[1] = v[1];
st[2] = v[2];
for (i = 3; i <= n; ++i) {
while (len >= 2 && sinABC(st[len - 1], st[len], v[i]) > 0)
--len;
st[++len] = v[i];
}
g << len << '\n';
for (i = 1; i <= len; ++i) {
g << fixed << setprecision(12) << st[i].first << ' ' << st[i].second << '\n';
}
return 0;
}