Cod sursa(job #2485373)

Utilizator bigmixerVictor Purice bigmixer Data 1 noiembrie 2019 14:00:37
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.15 kb
#include <bits/stdc++.h>
#define ll long long
#define all(a) (a).begin(), (a).end()
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz() size()
#define fr first
#define sc second
#define pb push_back
#define er erase
#define in insert
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define mp make_pair
#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
///#define cin fin
///#define cout fout
using namespace std;

const int mod=1e9+7;
const int mod1=998244353;
const double eps=1e-12;

int n;
pair<double,double>v[120005];

double cross(pair<double,double>O,pair<double,double>A,pair<double,double>B){
    return (A.fr-O.fr)*(B.sc-O.sc)-(A.sc-O.sc)*(B.fr-O.fr);
    //pozitiv stanga
    //negativ dreapta
}

int32_t main(){
  //  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    fout << fixed << setprecision(7);
    fin >> n;
    for(int i=1;i<=n;i++){
        fin >> v[i].fr >> v[i].sc;
    }
    sort(v+1,v+n+1);
    vector<pair<double,double>>upper;
    upper.push_back(v[1]);
    upper.push_back(v[2]);
    for(int i=3;i<=n;i++){
        if(cross(v[i],upper[upper.size()-2],upper[upper.size()-1])>=0){
            while(upper.size()>=2 && cross(v[i],upper[upper.size()-2],upper[upper.size()-1])>=0){
                upper.pop_back();
            }
            upper.push_back(v[i]);
        }
        else upper.push_back(v[i]);
    }
    int d=upper.size()+1;
    upper.push_back(v[n-1]);
    for(int i=n-2;i>=1;i--){
        if(cross(v[i],upper[upper.size()-2],upper[upper.size()-1])>=0){
            while(upper.size()>=d && cross(v[i],upper[upper.size()-2],upper[upper.size()-1])>=0){
                upper.pop_back();
            }
            upper.push_back(v[i]);
        }
        else upper.push_back(v[i]);
    }
    fout << upper.size()-1 << '\n';
    for(int i=0;i<upper.size()-1;i++){
        fout << upper[i].fr << ' ' << upper[i].sc << '\n';
    }
  //  cout << '\n';
}