Pagini recente » Cod sursa (job #2646977) | Cod sursa (job #29058) | Cod sursa (job #2012769) | Cod sursa (job #1742702) | Cod sursa (job #3359375)
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
#define MAX_N 120005
#define x first
#define y second
typedef pair<double,double> Point;
int n;
int head;
Point v[MAX_N];
int st[MAX_N];
double crossProduct(Point O, Point A, Point B){
return (A.x - O.x) * (B.y - O.y) - (B.x - O.x)*(A.y - O.y);
}
void convex_hull(){
sort(v+1,v+n+1);
head = 0;
for(int i = 1;i <= n; ++i){
while(head >= 2 && crossProduct(v[st[head-1]],v[st[head]],v[i]) <= 0)
head--;
st[++head] = i;
}
int sizeJos = head;
for(int i = n-1;i >= 1; --i){
while(head > sizeJos && crossProduct(v[st[head-1]],v[st[head]],v[i]) <= 0)
head--;
st[++head] = i;
}
cout << head - 1 << '\n';
for(int i = 1;i < head; ++i)
cout << v[st[i]].x << " " << v[st[i]].y << '\n';
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
cin >> n;
cout << setprecision(6) << fixed;
for(int i = 1;i <= n; ++i){
cin >> v[i].x >> v[i].y;
}
convex_hull();
return 0;
}