Pagini recente » Cod sursa (job #1150112) | Cod sursa (job #772137) | Cod sursa (job #75855) | Cod sursa (job #1487050) | Cod sursa (job #2981799)
#include <bits/stdc++.h>
using namespace std;
int const N=15e4;
#define float double
#define coord pair<float,float>
coord cord[N];
int n;
double area(coord A,coord B,coord C)
{
double rez=0;
rez+=A.first*B.second;
rez+=B.first*C.second;
rez+=C.first*A.second;
rez-=B.second*C.first;
rez-=C.second*A.first;
rez-=A.second*B.first;
return rez;
}
int Mystack[N];
int rez[N],reznr;
void solveST()
{
int poz=0;
for(int i=0;i<n;i++)
{
while(poz>1 && area(cord[Mystack[poz-2]],cord[Mystack[poz-1]],cord[i])>0)
poz--;
Mystack[poz++]=i;
}
reznr=poz;
for(int i=0;i<poz;i++)
rez[i]=Mystack[i];
}
void solveDR()
{
int poz=0;
for(int i=0;i<n;i++)
{
while(poz>1 && area(cord[Mystack[poz-2]],cord[Mystack[poz-1]],cord[i])<0)
poz--;
Mystack[poz++]=i;
}
for(int i=1;i<poz-1;i++)
rez[reznr+i-1]=Mystack[poz-i-1];
reznr+=poz-2;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
double x,y;
cin>>x>>y;
cord[i]={x,y};
}
sort(cord,cord+n);
solveST();
solveDR();
cout<<reznr<<'\n';
for(int i=0;i<reznr;i++)
cout<<cord[rez[i]].first<<' '<<cord[rez[i]].second<<'\n';
}