Pagini recente » Cod sursa (job #2261468) | Cod sursa (job #207406) | Cod sursa (job #703583) | Cod sursa (job #258536) | Cod sursa (job #2425890)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point{
double x, y;
}v[120100], st[120100];
int n, vf;
double delta(point A, point B, point C)
{
return A.x*B.y + C.x*A.y + B.x*C.y - C.x*B.y - A.x*C.y - B.x*A.y;
}
int compare1(point A, point B)
{
if(A.x==B.x)
return (A.y<B.y);
return (A.x<B.x);
}
int compare2(point B, point C)
{
return (delta(v[1],B,C) < 0);
}
int i;
int main()
{
f>>n;
for(i=1;i<=n;i++)
{
f>>v[i].x>>v[i].y;
}
sort(v+1,v+n+1,compare1);
st[1]=v[1];
sort(v+2,v+n+1,compare2);
st[2]=v[2];
vf = 2;
for(i=3;i<=n;i++)
{
while(vf>2 && delta(st[vf-1],st[vf],v[i])>0)vf--;
vf++;
st[vf]=v[i];
}
g<<vf<<'\n';
for(i=vf;i>=1;i--)
{
g<<fixed<<setprecision(6)<<st[i].x<<" ";
g<<fixed<<setprecision(6)<<st[i].y<<" ";
g<<'\n';
}
return 0;
}