Pagini recente » Cod sursa (job #1463085) | Cod sursa (job #1073223) | Cod sursa (job #1356580) | Cod sursa (job #2224874) | Cod sursa (job #883092)
Cod sursa(job #883092)
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
int n,i,j,k;
double a,b;
vector<int>s;
struct nod
{
double x;
double y;
}v[120005];
bool cmp(const nod a1,const nod b1)
{
return (a1.y-b)*(b1.x-a)<=(a1.x-a)*(b1.y-b);
}
int semn(int a,int b,int c)
{
double s=0;
s=v[a].x*v[b].y+v[b].x*v[c].y+v[a].y*v[c].x-v[b].y*v[c].x-v[c].y*v[a].x-v[b].x*v[a].y;
if (s<0) return 0;
return 1;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);a=999999999;b=999999999;
for (i=1;i<=n;i++)
{
scanf("%lf %lf",&v[i].x,&v[i].y);
if (a>v[i].x) a=v[i].x,b=v[i].y,k=i;else
if (a==v[i].x && b>v[i].y) b=v[i].y,k=i;
}
swap(v[k],v[1]);
sort(v+1,v+n+1,cmp);
s.push_back(0);
s.push_back(1);
s.push_back(2);
k=2;
for (i=3;i<=n;i++)
{
while (k>=2 && !semn(s[k-1],s[k],i)) k--,s.pop_back();
k++;
s.push_back(i);
}
printf("%d\n",k);
for(i=1;i<=k;i++) printf("%lf %lf\n",v[s[i]].x,v[s[i]].y);
return 0;
}