Pagini recente » Cod sursa (job #2251676) | Cod sursa (job #315421) | Cod sursa (job #1980742) | Cod sursa (job #2109213) | Cod sursa (job #1863790)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int nMax = 120003;
const double eps = 1e-12;
struct Point {
double x, y;
};
inline bool cmp(const Point A, const Point B) {
return A.y < B.y;
}
Point a[nMax];
bool viz[nMax];
int St[nMax];
inline double Semn(int i, int j, int k) {
return (a[j].x-a[i].x)*(a[k].y-a[i].y)-(a[j].y-a[i].y)*(a[k].x-a[i].x);
}
int main()
{
int n;
f >> n;
for(int i = 1; i <= n; i++) {
f >> a[i].x >> a[i].y;
}
sort(a + 1, a + n + 1, cmp);
int top = 0;
viz[2] = 1;
St[++top] = 1;
St[++top] = 2;
int semn = 1;
for(int i = 3; i ; i += semn) {
if(!viz[i]) {
while(top >= 2 && Semn(St[top - 1], St[top], i) < eps) {
viz[St[top]] = 0;
top--;
}
St[++top] = i;
viz[i] = 1;
}
if(i == n) {
semn = -1;
}
}
g << top - 1 << "\n";
for(int i = 2; i <= top; i++) {
g << fixed << a[St[i]].x << " " << a[St[i]].y << setprecision(6) << "\n";
}
return 0;
}