Pagini recente » Cod sursa (job #3165178) | Cod sursa (job #465767) | Cod sursa (job #2988012) | Cod sursa (job #2774187) | Cod sursa (job #2245960)
#include "bits/stdc++.h"
using namespace std;
const int NMax = 120003;
struct Point{
long double x, y;
};
Point Points[NMax];
int n;
long double UnghiPolar(Point A, Point B, Point C){
return (B.y - A.y) * (C.x - A.x) - (C.y - A.y) * (B.x - A.x);
}
bool cmp(Point x, Point y){
return (UnghiPolar(Points[1],x,y) >= 0);
}
int main(){
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin >> n;
int lr = 1;
for(int i = 1; i <= n; ++i){
cin >> Points[i].x >> Points[i].y;
if(Points[i].x == Points[lr].x){
if(Points[i].y < Points[lr].y){
lr = i;
}
}
if(Points[i].x < Points[lr].x){
lr = i;
}
}
swap(Points[lr], Points[1]);
sort(Points + 2, Points + 1 + n, cmp);
/*for(int i = 1; i <= n; ++i){
cout << Points[i].x << ' ' << Points[i].y << '\n';
}*/
int top = 0;
int st[NMax];
st[++top] = 1;
st[++top] = 2;
for(int i = 3; i <= n; ++i){
while(top && UnghiPolar(Points[st[top - 1]], Points[st[top]], Points[i]) < 0){
top--;
}
st[++top] = i;
}
cout << top << '\n';
for(int i = top; i >= 1; --i){
cout << fixed << setprecision(13) << Points[st[i]].x << ' ' << Points[st[i]].y << '\n';
}
}