Cod sursa(job #2552738)

Utilizator vladth11Vlad Haivas vladth11 Data 21 februarie 2020 10:10:06
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " <, x << "\n";

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;

struct point
{
    dd x,y;
};
bool wecmp(point a,point b){
    if(a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}
vector <point> points;
vector  <point> convex_hull;
int n,vf;
point stiva[120001];
bool prost(point a, point b, point c){
    double rez = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
    return (rez < 0);
}
int main()
{
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        point punct;
        cin >> punct.x >> punct.y;
        points.push_back(punct);
    }
    sort(points.begin(),points.end(),wecmp);
    stiva[++vf] = points[0];
    stiva[++vf] = points[1];
    for(int i = 2;i < n;i++){
        while(vf > 1 && prost(stiva[vf-1],stiva[vf],points[i])){
            vf--;
        }
        stiva[++vf] = points[i];
    }
    int i;
  for(i = 1;i <= vf;i++)
    convex_hull.push_back(stiva[i]);
    vf = 0;
    reverse(points.begin(),points.end());
     stiva[++vf] = points[0];
    stiva[++vf] = points[1];
    for(int i = 2;i < n;i++){
        while(vf > 1 && prost(stiva[vf-1],stiva[vf],points[i])){
            vf--;
        }
        stiva[++vf] = points[i];
    }
   for(i = 2;i <= vf - 1;i++)
    convex_hull.push_back(stiva[i]);
    cout << convex_hull.size() << "\n";
    for(auto x : convex_hull){
        cout << fixed << setprecision(12) << x.x << " " << fixed << setprecision(12) << x.y << "\n";
    }
    return 0;
}