Cod sursa(job #2473204)

Utilizator carburatorMitica Carburator carburator Data 13 octombrie 2019 14:01:14
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct elem{double x,y,pan,dist;}; elem p[120001]; int N,i,contor,poz; bool okay; double xi,yi,x2,y2,x3,y3;
 vector<elem> v;
bool comp(elem a1, elem a2){if(a1.y!=a2.y) return a1.y<a2.y; return a1.x<a2.x;}
bool comp2(elem a1, elem a2){if(a1.pan!=a2.pan) return a1.pan>a2.pan; return a1.dist>a2.dist;}
int main()
{
    //citire, sortare dupa y, si x (ptr a obtine punctul cel mai de jos), apoi calculat pante dupa punctul respectiv; folosim cos, injectiva pe [0,pi]
    fin>>N; for(i=1;i<=N;i++)fin>>p[i].x>>p[i].y; sort(p+1,p+N+1,comp); xi=p[1].x; yi=p[1].y;
    for(i=2;i<=N;i++){x2=p[i].x; y2=p[i].y; p[i].dist=sqrt((x2-xi)*(x2-xi)+(y2-yi)*(y2-yi)); p[i].pan=(x2-xi)/p[i].dist;}
    sort(p+2,p+N+1,comp2);
    //    for(i=1;i<=N;i++)fout<<p[i].x<<" "<<p[i].y<<'\n';
    v.push_back(p[1]); v.push_back(p[2]); contor=2;

    while(contor<N){ contor++;
    v.push_back(p[contor]);
    okay=1; poz=v.size()-3;
    while(okay){xi=v.at(poz).x; yi=v.at(poz).y; x2=v.at(poz+1).x; y2=v.at(poz+1).y; x3=v.at(poz+2).x; y3=v.at(poz+2).y;
        if((x2-xi)*(y3-yi)-(x3-xi)*(y2-yi)<0.00){okay=1; v.erase(v.begin()+(poz+1)); poz=v.size()-3;}
        else okay=0;
    }
    }
    fout<<v.size()<<'\n';
    fout<<std::fixed;
    for(i=0;i<v.size();i++)fout<<std::setprecision(6)<<v.at(i).x<<" "<<v.at(i).y<<'\n';
    return 0;
}