Pagini recente » Cod sursa (job #513547) | Cod sursa (job #2210999) | Cod sursa (job #675409) | Cod sursa (job #658311) | Cod sursa (job #3194191)
#include <bits/stdc++.h>
#pragma GCC optimize ("03")
using namespace std;
#define INFILE "infasuratoare.in"
#define OUTFILE "infasuratoare.out"
const int N_MAX = 120005;
const double INF = 1e9;
struct Point {
double x, y;
Point() : x(0), y(0) {}
Point(double _x, double _y) : x(_x), y(_y) {}
};
int n;
Point v[N_MAX];
vector<Point> ans;
double triangleArea(Point &a, Point &b, Point &c){
return (
a.x * b.y - a.y * b.x +
b.x * c.y - b.y * c.x +
c.x * a.y - c.y * a.x
);
}
bool compare(Point &a, Point &b) {
return (triangleArea(v[0], a, b) > 0);
}
void solve(){
cin >> n;
for(int i = 0; i < n; ++i){
cin >> v[i].x >> v[i].y;
if(v[i].x < v[0].x){
swap(v[0], v[i]);
}
}
sort(v + 1, v + n, compare);
ans.push_back(v[0]);
for(int i = 1; i < n; ++i){
while(ans.size() > 1 && triangleArea(ans[ans.size() - 2], ans[ans.size() - 1], v[i]) <= 0){
ans.pop_back();
}
ans.push_back(v[i]);
}
cout << ans.size() << '\n';
for(auto it : ans){
cout << fixed << setprecision(6) << it.x << " " << it.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;
}