Pagini recente » Cod sursa (job #580705) | craciun-viteza-2 | infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #522250) | Cod sursa (job #1457214)
#include <bits/stdc++.h>
#define pdd pair<double,double>
using namespace std;
vector<pdd> P;
void Read()
{
double x,y;
int N;
scanf("%d",&N);
for(int i = 1; i <= N; ++i){
scanf("%lf%lf",&x,&y);
P.push_back({x,y});
}
sort(P.begin(),P.end());
}
bool broken(pdd A, pdd B, pdd C)
{
return (B.first - A.first)*(C.second - A.second) -
(B.second - A.second)*(C.first - A.first) > 0;
}
void Andrew_Hull()
{
vector<pdd> Up,Dw;
int vfu = 0,vfd = 0;
for(auto it : P){
while(vfu >= 2 && broken(Up[vfu-1],Up[vfu-2],it))
Up.pop_back(),--vfu;
while(vfd >= 2 && broken(Dw[vfd-2],Dw[vfd-1],it))
Dw.pop_back(),--vfd;
Up.push_back(it);++vfu;
Dw.push_back(it);++vfd;
}
printf("%d\n",(int)Up.size() + (int)Dw.size() - 2);
for(int i = 0; i < (int)Up.size()-1; ++i)
printf("%f %f\n",Up[i].first,Up[i].second);
for(int i = (int)Dw.size()-1; i >= 1; --i)
printf("%f %f\n",Dw[i].first,Dw[i].second);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
Read();
Andrew_Hull();
return 0;
}