Cod sursa(job #2660571)

Utilizator NashikAndrei Feodorov Nashik Data 19 octombrie 2020 19:29:16
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
//#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("infasuratore.in");
ofstream cout("infasuratoare.out");
pair<double,double> v[120005];
int cnt=2;
int st[120005];
double dist2(pair<double,double> a,pair<double,double> b){
    return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
/*bool mysort(pair<double,double> a,pair<double,double> b){
    if(a.first<=v[1].first and b.first>=v[1].first){
        return false;
    }
    if(a.first>=v[1].first and b.first<=v[1].first){
        return true;
    }
    if((a.first-v[1].first)*(b.second-v[1].second)==(b.first-v[1].first)*(a.second-v[1].second))
        return dist2(a,v[1])>dist2(b,v[1]);
    return (a.first-v[1].first)*(b.second-v[1].second)>(b.first-v[1].first)*(a.second-v[1].second);
}
*/
double calc_area(int a,int b,int c){
    double a1=v[a].first,
    a2=v[a].second,
    b1=v[b].first,
    b2=v[b].second,
    c1=v[c].first,
    c2=v[c].second;
    return (a1*b2+b1*c2+c1*a2-b2*c1-c2*a1-a2*b1);
}
bool verif(int c){
    if(cnt<=2)
        return true;
    int a=st[cnt-1];
    int b=st[cnt];
    if(calc_area(a,b,c)<=0)
        return false;
    return true;
}
int main()
{
    int n,mini=0;
    cin>>n;
    v[0].second=1000000001;
    for(int i=1;i<=n;i++){
        cin>>v[i].first>>v[i].second;
        if(v[mini].second>v[i].second)
            mini=i;
    }
    swap(v[1],v[mini]);
    //sort(v+2,v+n+1,mysort);
    v[++n]=v[1];
    st[1]=1;
    st[2]=2;
    for(int i=3;i<=n;i++){
        while(cnt>3 and verif(i)==false){
            cnt--;
        }
        st[++cnt]=i;
    }
    cnt--;
    cout<<cnt<<"\n";
    for(int i=1;i<=cnt;i++){
        cout<<v[st[i]].first<<" "<<v[st[i]].second<<"\n";
    }
    return 0;
}