Cod sursa(job #1894993)

Utilizator RaZxKiDDavid Razvan RaZxKiD Data 27 februarie 2017 18:34:01
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>

using namespace std;

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

int n;
struct pct{
    double x,y;
}refe;
vector<pct> V,S;

pct secback(){
    return S[S.size()-2];
}
void read(){
    double x,y;
    in>>n;
    for(int i=1;i<=n;i++){
        in>>x>>y;
        V.push_back({x,y});
    }
}
double det(double x1, double y1, double x2, double y2, double x3, double y3){
    return (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
}
bool cmp(pct a, pct b){
    return det(refe.x,refe.y,a.x,a.y,b.x,b.y)<0;
}
void solve(){
    int xmin=1000000001,ymin=1000000001,imin;
    for(int i=0;i<n;i++){
        if(V[i].x<xmin){
            xmin=V[i].x;
            ymin=V[i].y;
            imin=i;
        }
        else if(V[i].x==xmin&&V[i].y<ymin){
            ymin=V[i].y;
            imin=i;
        }
    }
    refe.x=xmin;
    refe.y=ymin;
    swap(V[0],V[imin]);
    sort(V.begin()+1,V.end(),cmp);
    S.push_back(V[0]);
    S.push_back(V[1]);
    for(int i=2;i<n;i++){
        while(S.size()>=2&& det(secback().x,secback().y, S.back().x,S.back().y, V[i].x, V[i].y) > 0)
            S.pop_back();
        S.push_back(V[i]);
    }
    out<<S.size()<<"\n";
    for(auto it= S.rbegin();it!=S.rend();it++){
        out<<setprecision(6)<<fixed<<(*it).x<<" "<<(*it).y;
        out<<"\n";
    }
}
int main(){
    read();
    solve();
    return 0;
}