Pagini recente » Cod sursa (job #923754) | Cod sursa (job #1565580) | Cod sursa (job #2560165) | Cod sursa (job #3182719) | Cod sursa (job #2936686)
#include <bits/stdc++.h>
#define nmax 120003
#define float double
#define inf FLT_MAX
#define pi 3.14159
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct pt{
float x,y;
};
int st;
pt s[nmax];
float cross(const pt &a, const pt &b, const pt &c)
{
float cr=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
//g<<a.x<<','<<a.y<<' '<<b.x<<','<<b.y<<' '<<c.x<<','<<c.y<<' '<<cr<<'\n';
return cr;
}
bool cmp(const pt &a, const pt &b)
{
return cross(s[0],a,b)<0;
}
int n;
pt stk[nmax];
int k;
int main()
{
f>>n;
for(int i=0;i<n;i++)
{
f>>s[i].x>>s[i].y;
if(s[i].x<s[st].x) st=i;
else if(s[i].x==s[st].x&&s[i].y<s[st].y) st=i;
}
swap(s[0],s[st]);
sort(s+1,s+n,cmp);
stk[k++]=s[0];
for(int i=1;i<n;i++)
{
auto e=s[i];
//if(e.x==st.x&&e.y==st.y) continue;
while(k>=2&&cross(stk[k-2],stk[k-1],e)>0) {k--;}
stk[k++]=e;
//g<<e.x<<','<<e.y<<','<<k<<'\n';
}
g<<k<<'\n';
for(int i=k-1;i>=0;i--)
{
g<<fixed<<setprecision(6)<<stk[i].x<<' '<<stk[i].y<<'\n';
}
return 0;
}