Pagini recente » Diferente pentru problema/joc3 intre reviziile 1 si 2 | Cod sursa (job #1640999) | Cod sursa (job #2611927) | Cod sursa (job #1699906) | Cod sursa (job #1568853)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct{float x,y;};
punct a[200001],st[200001];
int n,i,v;
bool cmp(punct b,punct c)
{
return (((c.x-a[0].x)*(b.y-a[0].y))<((b.x-a[0].x)*(c.y-a[0].y)));
}
bool semn(punct a,punct b,punct c)
{
return ((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x)<0);
}
int main()
{
a[0].x=a[0].y=1<<31-1;
f>>n;
for (i=1;i<=n;i++){
f>>a[i].x>>a[i].y;
if (a[0].x>a[i].x)
a[0].x=a[i].x,a[0].y=a[i].y;
else if (a[0].x==a[i].x)
if (a[0].y>a[i].y)
a[0].y=a[i].y;
}
sort(a+1,a+n+1,cmp);
st[v=1]=a[0];
for (i=1;i<=n;i++)
if (!(a[i].x==a[0].x && a[i].y==a[0].y)){
while(v>=2 && semn(st[v-1],st[v],a[i]))
v--;
st[++v]=a[i];
}
g<<v<<'\n';
g<<fixed<<setprecision(6);
for (i=2;i<=v;i++)
g<<st[i].x<<' '<<st[i].y<<'\n';
g<<st[1].x<<' '<<st[1].y<<'\n';
return 0;
}