Pagini recente » Cod sursa (job #239775) | Cod sursa (job #1612822) | Cod sursa (job #1159955) | Cod sursa (job #2419415) | Cod sursa (job #1605187)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct{float x,y;};
int n,i,l,varf;
punct a[100001],st,v[100001],sti[100001];
bool cmp(punct a,punct b)
{
return (a.y-st.y)*(b.x-st.x)-(b.y-st.y)*(a.x-st.x)<0;
}
float det(punct a,punct b,punct c)
{
return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-a.x*c.y-b.x*a.y;
}
int main()
{
f>>n;
for (i=1;i<=n;i++)
f>>a[i].x>>a[i].y;
st=a[1];
for (i=2;i<=n;i++)
if (a[i].x<st.x) st=a[i];
else if (a[i].x==st.x)
if (a[i].y<st.y)
st=a[i];
for (i=1;i<=n;i++)
if (a[i].x!=st.x || a[i].y!=st.y) v[++l]=a[i];
sort(v+1,v+l+1,cmp);
sti[varf=1]=st;
for (i=1;i<=l;i++)
{
while(varf>=2 && det(sti[varf-1],sti[varf],v[i])<0)
varf--;
sti[++varf]=v[i];
}
g<<varf<<'\n';
for (i=2;i<=varf;i++)
g<<sti[i].x<<' '<<sti[i].y<<'\n';
g<<sti[1].x<<' '<<sti[1].y;
return 0;
}