Pagini recente » Cod sursa (job #2341137) | Cod sursa (job #2311774) | Cod sursa (job #3249276) | Cod sursa (job #3001062) | Cod sursa (job #3039525)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <iomanip>
using namespace std;
string filename = "infasuratoare";
#ifdef LOCAL
ifstream fin("input.in");
ofstream fout("output.out");
#else
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");
#endif
const int NMAX = 120000;
struct Point{
double x, y;
}v[NMAX + 1];
bool cmp(Point a, Point b){
return a.x < b.x;
}
double area(Point a, Point b, Point c){
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}
signed main(){
int n;
fin >> n;
for(int i = 1; i <= n; i++){
fin >> v[i].x >> v[i].y;
}
sort(v + 1, v + n + 1, cmp);
vector <int> up;
up.push_back(1);
for(int i = 2; i <= n; i++){
while((int)up.size() > 1 && area(v[up[(int)up.size() - 2]], v[up.back()], v[i]) >= 0){
up.pop_back();
}
up.push_back(i);
}
vector <int> down;
down.push_back(1);
for(int i = 2; i <= n; i++){
while((int)down.size() > 1 && area(v[down[(int)down.size() - 2]], v[down.back()], v[i]) <= 0){
down.pop_back();
}
down.push_back(i);
}
vector <int> ch = up;
down.pop_back();
reverse(down.begin(), down.end());
down.pop_back();
for(int x : down){
ch.push_back(x);
}
reverse(ch.begin(), ch.end());
fout << fixed << setprecision(12);
fout << ch.size() << '\n';
for(int ind : ch){
fout << v[ind].x << ' ' << v[ind].y << '\n';
}
return 0;
}