Cod sursa(job #3321272)

Utilizator aaagabiTurbinca Gabriel aaagabi Data 8 noiembrie 2025 20:18:11
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef long long ll;
typedef long double ld;
struct punct
{
   ld x,y;
   int id;
   punct operator-(const punct &other)
   {
      return {x-other.x,y-other.y};
   }
   bool operator==(const punct &other)
   {
      return x==other.x&&y==other.y;
   }
   bool operator<(const punct &other)
   {
      return x<other.x||x==other.x&&y<other.y;
   }
};
ld cross(punct a,punct b,punct c)
{
   return (b.y-a.y)*(c.x-a.x)-(b.x-a.x)*(c.y-a.y);
}
punct zero;
ld dot(punct a,punct b,punct c)
{
   return (b.x-a.x)*(c.x-a.x)+(b.y-a.y)*(c.y-a.y);
}
ld dist(punct a,punct b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(punct a,punct b)
{
   return cross(zero,a,b)<0||cross(zero,a,b)==0&&dist(zero,a)<dist(zero,b);
}
vector <punct> convexhull(vector <punct>& pts)
{
   if(pts.size()<=2)
      return pts;
   vector <punct> st;
   for(int i=0;i<pts.size();i++)
      if(pts[i]<pts[0])
         swap(pts[i],pts[0]);
   zero=pts[0];
   sort(pts.begin()+1,pts.end(),cmp);
   st.push_back(pts[0]);
   st.push_back(pts[1]);
   for(int i=2;i<pts.size();i++)
   {
      while(st.size()>=2&&cross(st[st.size()-2],st.back(),pts[i])>=0)
         st.pop_back();
      st.push_back(pts[i]);
   }
   return st;
}
int main()
{
    int n;
    fin>>n;
    vector <punct> a(n);
    for(int i=0;i<n;i++)
        fin>>a[i].x>>a[i].y;
    auto b=convexhull(a);
    fout<<b.size()<<'\n';
    for(auto p:b)
        fout<<fixed<<setprecision(12)<<p.x<<' '<<p.y<<'\n';
    return 0;
}