Pagini recente » Cod sursa (job #2890171) | Cod sursa (job #336863) | Cod sursa (job #414958) | Cod sursa (job #2270913) | Cod sursa (job #2990974)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
const int N_MAX = 120005;
struct Points{
double x, y;
};
Points v[N_MAX];
int n;
int stk[N_MAX];
double solve (Points a, Points b, Points c){
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
inline bool sort_unghi (Points a, Points b){
return solve(v[1], a, b) < 0;
}
int main(){
ios_base::sync_with_stdio(false);
fin >> n;
for (int i = 1; i <= n; i++){
fin >> v[i].x >> v[i].y;
}
int pos = 1;
for (int i = 2; i <= n; i++){
if (make_pair(v[i].x, v[i].y) < make_pair(v[pos].x, v[pos].y)){
pos = i;
}
}
swap(v[1], v[pos]);
sort(v + 2, v + n + 1, sort_unghi);
stk[++stk[0]] = 1;
stk[++stk[0]] = 2;
for (int i = 3; i <= n; i++){
while (stk[0] >= 2 && solve(v[stk[stk[0] - 1]], v[stk[stk[0]]], v[i]) > 0){
--stk[0];
}
stk[++stk[0]] = i;
}
fout << stk[0] << '\n';
for (int i = 1; i <= stk[0]; i++){
fout << fixed << setprecision(9) << v[stk[i]].x << " " << v[stk[i]].y << '\n';
}
}