Pagini recente » Cod sursa (job #1709654) | Cod sursa (job #60537) | Cod sursa (job #720500)
Cod sursa(job #720500)
#include<fstream>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{
double x,y;
} p[120010];
int n,pi/*punct initial*/;
int s[120010];
int st[120010],vf,cur;
void citire()
{
f>>n;
for(int i=1;i<=n;i++)
f>>p[i].x>>p[i].y;
f.close();
}
int comp(int a,int b)
{
return (double)(p[a].x-p[pi].x)*(p[b].y-p[pi].y)<(double)(p[b].x-p[pi].x)*(p[a].y-p[pi].y);
}
long double semn(int x1, int x2, int x3)
{
return (long double)p[x1].x*p[x2].y+p[x2].x*p[x3].y+p[x3].x*p[x1].y-p[x3].x*p[x2].y-p[x1].x*p[x3].y-p[x2].x*p[x1].y;
}
int main()
{
citire();
p[0].x=p[0].y=inf;
for(int i=1;i<=n;i++)
if(p[i].x<p[pi].x)
pi=i;
for(int i=1;i<=n;i++)
if(i!=pi)
s[++s[0]]=i;
sort(s+1,s+s[0]+1,comp);
st[1]=pi;st[2]=s[1];vf=2;
for(int i=2;i<=s[0];i++)
{
cur=s[i];
while(semn(st[vf],st[vf-1],cur)<0&&vf>1)
{
st[vf--]=0;
}
st[++vf]=cur;
}
/*
while(semn(st[vf],st[vf-1],st[1])<0)
{
st[vf--]=0;
}
*/
g<<vf<<'\n';
for(int i=vf;i>0;i--)
g<<p[st[i]].x<<' '<<p[st[i]].y<<'\n';
return 0;
}