Pagini recente » Statistici Draghici Paul (Paul281881818818181991919191881818) | preoji/clasament/9 | Istoria paginii runda/daupentrumata/clasament | Istoria paginii runda/oni_2013_zi1_9/clasament | Cod sursa (job #2496157)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
//ifstream fin("input.in");
//ofstream fout("output.out");
struct Point {
double x,y;
};
vector<Point> p;
stack<Point> s;
int isLeft(const Point &P, const Point &Q, const Point &R) {
return ((Q.x - P.x) * (R.y - P.y) - (Q.y - P.y) * (R.x - P.x) > 0);
}
int comparer(const Point &P, const Point &Q) {
return isLeft(p[0], P, Q);
}
Point nextInStack(stack<Point> s) {
Point t = s.top();
s.pop();
Point sec = s.top();
s.push(t);
return sec;
}
int main() {
int n, tp, i;
fin>>n;
p.resize(n);
for(i = 0; i < n; i++)
fin>>p[i].x>>p[i].y;
for(i = 1; i < n; i++)
if(p[0].x > p[i].x || (p[0].x == p[i].x && p[0].y > p[i].y))
swap(p[0], p[i]);
sort(p.begin() + 1, p.end(), comparer);
s.push(p[0]);
s.push(p[1]);
for(int i = 2; i < n; i++) {
while(s.size() >= 2 && !isLeft(nextInStack(s), s.top(), p[i]))
s.pop();
s.push(p[i]);
}
int k = s.size();
vector<Point> convex_hull;
while(!s.empty()) {
convex_hull.push_back(s.top());
s.pop();
}
fout<<k<<endl;
for(int i = k - 1; i >= 0; i--)
fout<<fixed<<setprecision(6)<<convex_hull[i].x<<' '<<convex_hull[i].y<<'\n';
}