Pagini recente » Cod sursa (job #1179702) | Cod sursa (job #1786678) | Cod sursa (job #319569) | Cod sursa (job #1631954) | Cod sursa (job #916735)
Cod sursa(job #916735)
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
struct punct{
double x;
double y;
}a[120005];
int n,m,i,k;
double x,y,d;
vector<int>v;
int cmp(const punct a,const punct b)
{
if((a.x-x)*(b.y-y)<=(a.y-y)*(b.x-x))return 0;
else return 1;
}
int re(int x1,int x2,int x3)
{
d=a[x1].x*a[x2].y+a[x2].x*a[x3].y+a[x3].x*a[x1].y-(a[x1].y*a[x2].x+a[x2].y*a[x3].x+a[x3].y*a[x1].x);
if(d<0)return 0;
return 1;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
x=99999999;y=99999999;
for(i=1;i<=n;i++){
scanf("%lf",&a[i].x);
scanf("%lf",&a[i].y);
if(y>a[i].y){x=a[i].x;y=a[i].y;k=i;}
if(y==a[i].y)
if(x<a[i].x){x=a [i].x;y=a[i].y;k=i;}
}
swap(a[1],a[k]);
sort(a+1,a+n+1,cmp);
v.push_back(0);
v.push_back(1);
v.push_back(2);
m=2;
for(i=3;i<=n;i++){
while(m>=2 && re(v[m-1],v[m],i)==0){
m--;
v.pop_back();
}
m++;
v.push_back(i);
}
printf("%d\n",m);
for(i=1;i<=m;i++)printf("%f %f\n",a[v[i]].x,a[v[i]].y);
return 0;
}