Pagini recente » Cod sursa (job #577549) | Cod sursa (job #159946) | Cod sursa (job #170845) | Cod sursa (job #1710247) | Cod sursa (job #2201484)
#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];
inline 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));
}
inline bool cmp(pd a, pd b) {
return (sinABC(a, v[1], b) > 0);
}
int main() {
int i, n;
f >> n;
for (i = 1; i <= n; ++i)
f >> v[i].first >> v[i].second;
int pos = 1;
for (i = 2; i <= n; ++i)
if (v[i] < v[pos])
pos = i;
swap(v[1], v[pos]);
sort(v + 2, 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(6) << st[i].first << ' ' << st[i].second << '\n';
}
return 0;
}