Pagini recente » Cod sursa (job #3235692) | Cod sursa (job #3264195) | Cod sursa (job #2654638) | Cod sursa (job #2251901) | Cod sursa (job #3194180)
#include <bits/stdc++.h>
#pragma GCC optimize ("03")
using namespace std;
#define INFILE "infasuratoare.in"
#define OUTFILE "infasuratoare.out"
const double INF = 1e9;
struct Point {
double x;
double y;
Point() : x(0), y(0) {}
Point(double _x, double _y) : x(_x), y(_y) {}
};
int n;
Point minim(INF, INF);
vector<Point> v;
bool comp(Point a, Point b){
return (-minim.x + a.x) * (minim.y + b.y) > (-minim.y + a.y) * (-minim.x * b.x);
}
double determinant(Point &a, Point &b){
return (a.x * b.y - a.y * b.x);
}
int orientation(Point &a, Point &b, Point &c){
double ans = determinant(a, b) + determinant(b, c) + determinant(c, a);
if(ans < 0) return -1;
else if(ans == 0) return 0;
return 1;
}
void solve(){
cin >> n;
v.resize(n);
for(int i = 0; i < n; ++i){
double x, y; cin >> x >> y; v[i] = Point(x, y);
if(v[i].y < minim.y){
minim = Point(v[i].x, v[i].y);
swap(v[0], v[i]);
}
}
sort(v.begin() + 1, v.end(), comp);
// for(auto it : v){
// cout << fixed << setprecision(6) << it.x << " " << it.y << '\n';
// }
// cout << "============" << '\n';
vector<Point> ans;
ans.push_back(v[0]), ans.push_back(v[1]);
for(int i = 2; i < n; ++i){
while(ans.size() > 1 && orientation(ans[ans.size() - 2], ans[ans.size() - 1], v[i]) != -1){
ans.pop_back();
}
ans.push_back(v[i]);
}
cout << ans.size() << '\n';
for(auto nr : ans){
cout << fixed << setprecision(6) << nr.x << " " << nr.y << '\n';
}
}
int main(){
ios_base::sync_with_stdio(false);
freopen(INFILE, "r", stdin);
freopen(OUTFILE, "w", stdout);
cin.tie(0), cout.tie(0);
solve();
return 0;
}