Cod sursa(job #3288861)

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

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

#define MAXN 120000

struct point{
  double x,y;
};


bool operator<(const point &a,const point &b){
  return a.x<b.x||(a.x==b.x&&a.y<b.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;
  set<point> seen;

  while(!lower.empty()){
    if(seen.insert(lower.top()).second){
      rez.push_back(lower.top());
    }
    lower.pop();
  }

  while(!upper.empty()){
    if(seen.insert(upper.top()).second){
      rez.push_back(upper.top());
    }
    upper.pop();
  }

  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";
  reverse(convexpts.begin(),convexpts.end());
  for(auto pt:convexpts){
    cout<<fixed<<setprecision(6)<<pt.x<<" "<<pt.y<<"\n";
  }

  return 0;
}