Pagini recente » Monitorul de evaluare | Cod sursa (job #3346393) | Cod sursa (job #3350164) | Cod sursa (job #2853376) | Cod sursa (job #3349255)
//
// main.cpp
// Infasuratoare convexa
//
// Created by Andrada Minca on 25.03.2026.
//
#include <fstream>
#include <iomanip>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct punct{
long double x;
long double y;
};
vector<punct>v;
bool cmp(punct a,punct b)
{
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
long double arie(punct a,punct b,punct c)
{
return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-c.y*a.x-b.x*a.y;
}
const long double EPS=1e-15;
int main()
{
int n;
cin>>n;
v.resize(n);
for(int i=0;i<n;i++)
{
cin>>v[i].x>>v[i].y;
}
sort(v.begin(),v.end(),cmp);
vector<int> ans;
for(int i=0;i<n;i++)
{
while (ans.size()>=2&&arie(v[ans[ans.size()-2]],v[ans[ans.size()-1]],v[i]) < EPS)
{
ans.pop_back();
}
ans.push_back(i);
}
int t=ans.size();
for(int i=n-2;i>=0;i--)
{
while(ans.size()>t&&arie(v[ans[ans.size()-2]],v[ans[ans.size()-1]],v[i]) < EPS)
{
ans.pop_back();
}
ans.push_back(i);
}
ans.pop_back();
cout<<ans.size()<<'\n';
for(int i=0;i<ans.size();i++)
{
cout<<setprecision(13);
cout<<v[ans[i]].x<<" "<<v[ans[i]].y<<'\n';
//cout<<ans[i]<<" ";
}
return EXIT_SUCCESS;
}