Pagini recente » Cod sursa (job #2931342) | Cod sursa (job #2511703) | Cod sursa (job #3264925) | Cod sursa (job #2248981) | Cod sursa (job #3226930)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <cassert>
#include <random>
#include <chrono>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using ull = unsigned long long;
//using ll = long long;
//#define int __int128
//#define int ll
#define pii pair <int, int>
#define all(a) (a).begin(), (a).end()
#define fr first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define vt vector
#define FOR(a, b) for(int i = (a); i <= (b); i++)
#define FORr(a, b) for(int i = (a); i >= (b); i--)
#define sz(x) (int)(x).size()
#define YES cout << "YES\n"
#define NO cout << "NO\n"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rangerng(int l, int r){
return uniform_int_distribution<>(l, r)(rng);
}
string filename = "infasuratoare";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");
////////////////////////////////////////////////////////////////////////////////////
const int NMAX = 12e4;
struct Point{
double x, y;
}v[NMAX + 1];
double A(Point p1, Point p2, Point p3){
return p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);
}
bool cmp(Point a, Point b){
if(a.x == b.x){
return a.y < b.y;
}
return a.x < b.x;
}
void solve(){
int n;
fin >> n;
for(int i = 1; i <= n; i++){
fin >> v[i].x >> v[i].y;
}
sort(v + 1, v + n + 1, cmp);
vt <int> up;
vt <int> down;
for(int i = 1; i <= n; i++){
while(sz(up) >= 2 && A(v[up[sz(up) - 2]], v[up[sz(up) - 1]], v[i]) <= 0){
up.pop_back();
}
up.pb(i);
while(sz(down) >= 2 && A(v[down[sz(down) - 2]], v[down[sz(down) - 1]], v[i]) >= 0){
down.pop_back();
}
down.pb(i);
}
vt <int> ans = up;
reverse(all(down));
for(int i = 1; i + 1 < sz(down); i++){
ans.pb(down[i]);
}
fout << sz(ans) << '\n';
for(int ind : ans){
fout << fixed << setprecision(12) << v[ind].x << ' ' << v[ind].y << '\n';
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int T;
//cin >> T;
T = 1;
while(T--){
solve();
}
return 0;
}
/*
*/