Cod sursa(job #3288857)

Utilizator Andrei_PanaAndrei Pana Andrei_Pana Data 24 martie 2025 16:08:28
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.92 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>
using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

#define MAXN 120000

struct point{
  double x,y;

  bool operator==(point a){
    return (this->x==a.x&&this->y==a.y);
  }
};
vector<point> convexpts,points;
stack<point> stiva;

int area(point a,point b,point c){
  return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

vector<point> convex(vector<point> pts){
  sort(pts.begin(),pts.end(),[](point a,point b){
    return (a.x==b.x)?(a.y<b.y):(a.x<b.x);
  });

  stack<point> lower,upper;

  //Compute the lower points
  for(auto pt:pts){//begin from the lowest
    point top=pt,nexttop=pt;
    while(lower.size()>1&&area(nexttop,top,pt)<=0){
      top=lower.top();
      lower.pop();
      nexttop=lower.top();
    }
    if(area(nexttop,top,pt)>0){
      lower.push(top);
    }
    lower.push(pt);
  }

  //Compute the upper points
  for(int i=pts.size()-1;i>=0;i--){//begin from the greatest
    point pt=pts[i],top=pt,nexttop=pt;
    while(upper.size()>1&&area(nexttop,top,pt)<=0){
      top=upper.top();
      upper.pop();
      nexttop=upper.top();
    }
    if(area(nexttop,top,pt)>0){
      upper.push(top);
    }
    upper.push(pt);
  }

  //Combine the 2 sides
  vector<point> rez;

  while(!lower.empty()){
    rez.push_back(lower.top());
    lower.pop();
  }

  while(!upper.empty()){
    rez.push_back(upper.top());
    upper.pop();
  }

  //Remove the duplicates
  sort(rez.begin(),rez.end(),[](point a,point b){
    return (a.x==b.x)?(a.y<b.y):(a.x<b.x);
  });

  rez.erase(unique(rez.begin(),rez.end()),rez.end());

  return rez;
}

int main(){
  int n,i;
  double x,y;

  cin>>n;
  for(i=0;i<n;i++){
    cin>>x>>y;
    points.push_back({x,y});
  }
  convexpts=convex(points);

  cout<<convexpts.size()<<"\n";
  for(auto pt:convexpts){
    cout<<fixed<<setprecision(6)<<pt.x<<" "<<pt.y<<"\n";
  }

  return 0;
}