Cod sursa(job #1752131)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 2 septembrie 2016 20:23:31
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,i,varf,t,mins;
struct punct{
    double x,y;
}P[120001],S[120001];
double det(punct a,punct b,punct c){
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool comp(punct a,punct b){
      if (det(P[1],a,b)>0) return 0;
      return 1;
}
int main(){
    fin>>n;
    fin>>P[1].x>>P[1].y;
    mins=P[1].x;t=1;
    for (i=2;i<=n;i++){
        fin>>P[i].x>>P[i].y;
        if (mins>P[i].x){
            mins=P[i].x;
            t=i;
        }
          else
          if (mins==P[i].x && P[t].y>P[i].y) t=i;
    }
    swap(P[1],P[t]);
    sort(P+2,P+n+1,comp);
    varf=2;
    S[1]=P[1];
    S[2]=P[2];
    for (i=3;i<=n;i++){
        //Daca am avea pct coliniare, se elimina cel curent si se adauga pct mai departat
        while(varf>=2 && det(S[varf-1],S[varf],P[i])>0) varf--;
        varf++;
        S[varf]=P[i];
    }
    fout<<varf<<'\n';
    for (i=varf;i>=1;i--)
        fout<<fixed<<setprecision(12)<<S[i].x<<" "<<S[i].y<<'\n';
    fin.close();
    fout.close();
    return 0;
}