Pagini recente » Cod sursa (job #957567) | Cod sursa (job #1535720)
#include<iostream>
#include<vector>
#define pb push_back
using namespace std;
int N;
double X,Y;
struct pt {
double x, y;
};
vector<pt> a;
bool cmp (pt a, pt b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
bool cw (pt a, pt b, pt c) {
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
}
bool ccw (pt a, pt b, pt c) {
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
}
void convex_hull (vector<pt> & a) {
if (a.size() == 1) return;
sort (a.begin(), a.end(), &cmp);
pt p1 = a[0], p2 = a.back();
vector<pt> up, down;
up.push_back (p1);
down.push_back (p1);
for (size_t i=1; i<a.size(); ++i) {
if (i==a.size()-1 || cw (p1, a[i], p2)) {
while (up.size()>=2 && !cw (up[up.size()-2], up[up.size()-1], a[i]))
up.pop_back();
up.push_back (a[i]);
}
if (i==a.size()-1 || ccw (p1, a[i], p2)) {
while (down.size()>=2 && !ccw (down[down.size()-2], down[down.size()-1], a[i]))
down.pop_back();
down.push_back (a[i]);
}
}
a.clear();
for (size_t i=0; i<up.size(); ++i)
a.push_back (up[i]);
for (size_t i=down.size()-2; i>0; --i)
a.push_back (down[i]);
}
int main() {
//freopen("input.in","r",stdin);
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N);
for(int i=1;i<=N;++i) {
scanf("%lf%lf",&X,&Y);
pt p;
p.x = X;
p.y = Y;
a.pb(p);
}
convex_hull(a);
cout<<a.size()<<"\n";
for(int i=a.size()-1;i>=0;--i) {
printf("%.12lf %.12lf\n",a[i].x,a[i].y);
}
}