Pagini recente » Cod sursa (job #1098634) | Borderou de evaluare (job #1225344) | Cod sursa (job #738411) | Cod sursa (job #2410373) | Cod sursa (job #2159173)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct pct
{
double x,y;
};
pct v[120001],st[120001],vv[120001];
bool cmp(pct a,pct b){
if (a.x < b.x)
return true;
if (a.x == b.x)
if (a.y < b.y)
return true;
return false;
}
bool semn (pct p1,pct p2,pct p3) {
return (p2.x*p1.y+p3.x*p2.y+p1.x*p3.y-p1.x*p2.y-p2.x*p3.y-p3.x*p1.y)<0;
}
int main()
{
int n,i,vf = 0,lf;
in>>n;
for (int i = 0;i < n;i++)
in>>v[i].x >> v[i].y;
sort(v,v + n,cmp);
st[++vf]=v[0];
for (i = 1;i < n;i++) {
while (vf > 1 && !semn(st[vf-1],st[vf],v[i]))
vf--;
st[++vf]=v[i];
}
lf = vf;
for (int i = 1;i <= vf;i++)
vv[i]=st[i];
vf = 0;
st[++vf]=v[n - 1];
for (int i = n - 2;i >= 0;i--) {
while (vf > 1 && !semn(st[vf-1],st[vf],v[i]))
vf--;
st[++vf]=v[i];
}
for (int i = 2;i <= vf;i++)
vv[i+lf-1] = st[i];
lf = lf + vf - 2;
out<<lf<<"\n";
out<<fixed<<setprecision(6);
for(int i = 2;i <= lf;i++)
out<<vv[i].x<<" "<<vv[i].y<<"\n";
out<<vv[1].x<<" "<<vv[1].y;
return 0;
}