Pagini recente » Cod sursa (job #437388) | Cod sursa (job #3256697) | Cod sursa (job #653697) | Cod sursa (job #662437) | Cod sursa (job #2339203)
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <bitset>
#include <iomanip>
#define eps 1e-12
using namespace std;
int n,l=2,l1=2;
double x, y;
vector <pair<int,int>> pct;
vector <int> q, q1;
bitset <120005> viz;
double det(int p1, int p2, int p3)
{
return (pct[p2].first-pct[p1].first)*(pct[p3].second-pct[p1].second) - (pct[p2].second-pct[p1].second)*(pct[p3].first-pct[p1].first);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
cin>>n;
for(int i=0; i<n; ++i)
{
cin>>x>>y;
pct.push_back({x,y});
}
sort(pct.begin(),pct.end());
q.push_back(0);
q.push_back(1);
viz[1]=1;
for(int i=2; i<n; ++i)
{
if(viz[i])
continue;
while(q.size()>1 && det(q[l-2],q[l-1],i)<eps)
--l, viz[q[l]]=0, q.pop_back();
q.push_back(i);
++l;
viz[i]=1;
}
for(int i=n-1; i>=0; --i)
{
if(viz[i])
continue;
while(q.size()>1 && det(q[l-2],q[l-1],i)<eps)
--l, viz[q[l]]=0, q.pop_back();
q.push_back(i);
++l;
viz[i]=1;
}
cout<<l-1<<"\n";
q.erase(q.begin());
cout<<fixed<<setprecision(6);
for(int i : q)
cout<<pct[i].first<<" "<<pct[i].second<<"\n";
return 0;
}