Cod sursa(job #3309767)

Utilizator Maryy_1369Gociu Maria Anastasia Maryy_1369 Data 8 septembrie 2025 18:28:51
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include<deque>
#include<algorithm>
#include<vector>
#include<bits/stdc++.h>
#define x first
#define y second
#define int long long
#define double long double
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair<double,double>v[120022];
vector<pair<double,double>>res;

double deter(double x1,double y1,double x2,double y2,double x3,double y3){
  return x1*y2+x2*y3+x3*y1-y1*x2-y2*x3-y3*x1;
}
bool comp(pair<double,double>a,pair<double,double>b){
   if(deter(v[0].x,v[0].y,a.x,a.y,b.x,b.y)>0)return 1;
   if(deter(v[0].x,v[0].y,a.x,a.y,b.x,b.y)<0)return 0;
   return a.x<b.x;
}
signed main()
{
    int n;
    fin>>n;
    fin>>v[0].x>>v[0].y;
    for(int i=1;i<n;i++){
         fin>>v[i].x>>v[i].y;
         if(v[i].x<v[0].x || (v[i].x==v[0].x && v[i].y < v[0].y))swap(v[0],v[i]);
    }
    v[n]=v[0];
    sort(v+1,v+n,comp);
    res.push_back(v[0]);
    for(int i=1;i<=n;i++){
        bool lb=1;
        while(res.size()>=2 && lb){
             lb=0;
             pair<double,double>alf=res.back();
             res.pop_back();
             if(deter(res.back().x,res.back().y,alf.x,alf.y,v[i].x,v[i].y)<=0)lb=1;
             else res.push_back(alf);
        }
        res.push_back(v[i]);
    }
    res.pop_back();
    fout<<res.size()<<endl;
    for(auto x:res){
        fout<<setprecision(8)<<fixed<<x.x<<" "<<x.y<<endl;
    }
    return 0;
}