Pagini recente » Cod sursa (job #2689717) | preoji_bv_2017_1_10 | Istoria paginii runda/usu10mii/clasament | preoji/clasament/10 | Cod sursa (job #2496150)
#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 st[120005];
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 cmp(const Point &P, const Point &Q) {
return isLeft(p[1], 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;
fin>>n;
p.resize(n+1);
for(int i=1;i<=n;i++)
fin>>p[i].x>>p[i].y;
for(int i=2;i<=n;i++)
if(p[1].x>p[i].x || (p[1].x==p[i].x && p[1].y>p[i].y))
swap(p[1],p[i]);
sort(p.begin() + 2, p.end(), cmp);
/*st[1]=1; st[2]=2;
tp=2;
for(int i=3;i<=n;i++){
while(tp>=2 && !isLeft(p[st[tp-1]],p[st[tp]],p[i])) --tp;
st[++tp]=i;
}
fout<<tp<<'\n';
for(int i=1;i<=tp;i++)
fout<<fixed<<setprecision(6)<<p[st[i]].x<<' '<<p[st[i]].y<<'\n';
*/
s.push(p[1]);
s.push(p[2]);
for(int i = 3; 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';
}