Cod sursa(job #2937614)

Utilizator PostoacaMateiMatei Postoaca PostoacaMatei Data 10 noiembrie 2022 18:29:17
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int n;

struct punct{
    double x,y;
}v[120001],stjs,drss;

vector<punct>S1;
vector<punct>S2;

void Citire(){
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;
}

int cmp(punct a,punct b){
    if(a.x<b.x || (a.x==b.x && a.y<b.y))
        return 1;
    return 0;
}

int getOrientation(punct P1, punct P2, punct P3){
	int det = (P2.x-P1.x)*(P3.y-P1.y)-(P3.x-P1.x)*(P2.y-P1.y);
	if (det > 0)
		return 0;
	if (det < 0)
		return 1;
	return 2;
}

int Finder(){
    int rez=0,minim=10000;
    for(int i=0;i<S1.size();i++)
        if(S1[i].y<minim)
            minim=S1[i].y,rez=i;
    return rez;
}

int main()
{
    Citire();
    sort(v+1,v+n+1,cmp);
    S1.push_back(v[1]);
    S1.push_back(v[2]);
    for(int i=3;i<=n;i++){
        while(S1.size() > 1 && getOrientation(S1[S1.size()-2],S1[S1.size()-1],v[i])==1){
            S1.pop_back();
        }
        S1.push_back(v[i]);
    }
    S2.push_back(v[n]);
    S2.push_back(v[n-1]);
    for(int i=n-3;i>=1;i--){
        while(S2.size() > 1 && getOrientation(S2[S2.size()-2],S2[S2.size()-1],v[i])==1){
            S2.pop_back();
        }
        S2.push_back(v[i]);
    }
    fout<<S1.size()+S2.size()-2<<"\n";
    int start=Finder();
    for(int i=start;i<S1.size();i++)
        fout<<fixed<<setprecision(14)<<S1[i].x<<" "<<S1[i].y<<"\n";
    for(int i=1;i<S2.size()-1;i++)
        fout<<fixed<<setprecision(14)<<S2[i].x<<" "<<S2[i].y<<"\n";
    for(int i=start-1;i>=0;i--)
        fout<<fixed<<setprecision(14)<<S1[i].x<<" "<<S1[i].y<<"\n";
    return 0;
}