Pagini recente » Cod sursa (job #2707557) | Cod sursa (job #240014) | Cod sursa (job #1573090) | Cod sursa (job #2149331) | Cod sursa (job #2521543)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int maxn = 120005;
const double ZERO = 1e-12;
struct point {
double x, y;
bool operator < (point t) const {
return (x < t.x) || (x == t.x && y < t.y);
}
};
int n, s[maxn], top;
bitset<maxn> in;
point a[maxn];
double crossProduct(point o, point a, point b) {
return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}
int main() {
fin >> n;
for(int i = 1; i <= n; ++i)
fin >> a[i].x >> a[i].y;
sort(a + 1, a + n + 1);
in[2] = 1;
s[++top] = 1;
s[++top] = 2;
for(int i = 1; i <= n; ++i) {
if(in[i] == 1) continue;
while(top >= 2 && crossProduct(a[s[top - 1]], a[s[top]], a[i]) < ZERO) {
in[s[top]] = 0;
--top;
}
s[++top] = i;
in[i] = 1;
}
for(int i = n - 1; i >= 1; --i) {
if(in[i] == 1) continue;
while(top >= 2 && crossProduct(a[s[top - 1]], a[s[top]], a[i]) < ZERO) {
in[s[top]] = 0;
--top;
}
s[++top] = i;
in[i] = 1;
}
fout << fixed;
fout << top - 1 << "\n";
for(int i = 1; i < top; ++i)
fout << setprecision(6) << a[s[i]].x << " " << a[s[i]].y << "\n";
return 0;
}