Cod sursa(job #2087466)

Utilizator valentinoltyanOltyan Valentin valentinoltyan Data 13 decembrie 2017 18:24:01
Problema Infasuratoare convexa Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#define x first
#define y second
using namespace std;

const double EPS = 1e-12;
pair<double,double>v[120005];
vector<pair<double,double>>sol1;
vector<pair<double,double>>sol2;
int n;
double det(pair<double,double>a,pair<double,double>b,pair<double,double>c)
{
    return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
void solve()
{
    sol1.push_back({v[0].x,v[0].y});
    sol1.push_back({v[1].x,v[1].y});
    for(int i=2;i<n;i++)
    {
        int m=sol1.size();
        while(double p=det(sol1[m-2],sol1[m-1],v[i])>EPS &&m>1)
        {
            m--;
            sol1.pop_back();
        }
        sol1.push_back({v[i].x,v[i].y});
    }
    sol2.push_back({v[0].x,v[0].y});
    sol2.push_back({v[1].x,v[1].y});
    int d=sol2.size();
        for(int i=2;i<n;i++)
    {
        int m=sol2.size();
        while(double p=det(sol2[m-2],sol2[m-1],v[i])<EPS&&p>-EPS &&m>d)
        {
            m--;
            sol2.pop_back();
        }
        sol2.push_back({v[i].x,v[i].y});
    }
}
int main()
{
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    f>>n;
    for(int i=0;i<n;i++)
    {
        double a,b;
        f>>a>>b;
        v[i]={a,b};
    }
    sort(v,v+n);
    for(int i=0;i<n;i++)
        cout<<v[i].x<<" "<<v[i].y<<"\n";
    cout<<endl;
    solve();
    g<<sol1.size()+sol2.size()-3<<"\n";
    g<<fixed;
    for(int i=2;i<sol2.size();i++)
        g<<sol2[i].x<<" "<<sol2[i].y<<"\n";
    for(int i=sol1.size()-2;i>=0;i--)
        g<<sol1[i].x<<" "<<sol1[i].y<<"\n";
    return 0;
}