Pagini recente » Cod sursa (job #2181650) | Cod sursa (job #969487) | Cod sursa (job #637883) | Cod sursa (job #1603598) | Cod sursa (job #2173772)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int nMax = 120005;
const double eps = 1e-12;
struct Pct{
double x, y;
};
inline bool cmp (const Pct &A, const Pct &B) {
return A.y < B.y;
}
Pct a[nMax];
int St[nMax];
bool viz[nMax];
inline double Check(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;
St[++top] = 1;
St[++top] = 2;
viz[2] = 1;
int semn = 1;
for(int i = 3; i; i += semn) {
if(!viz[i]) {
while(top >= 2 && Check(St[top - 1], St[top], i) < eps) { ///le scot pe alea knn
viz[St[top]] = 0;
top--;
}
St[++top] = i;
viz[i] = 1;
}
if(i == n) {
semn = -1;
}
}
g << top - 1 << "\n";
for(int i = 1; i < top; i++){
g << fixed << a[St[i]].x << " " << a[St[i]].y << setprecision(6) << "\n";
}
return 0;
}