Pagini recente » Cod sursa (job #557565) | Cod sursa (job #192878) | Cod sursa (job #3138500) | Cod sursa (job #1643470) | Cod sursa (job #411391)
Cod sursa(job #411391)
#include<vector>
#include<algorithm>
using namespace std;
typedef pair <double,double> p;
#define x first
#define y second
#define NMAX 120005
#define ld long double
p a[NMAX];
int st[NMAX];
int n,i,Min=1,top;
inline bool cmp(const p &A,const p &B)
{
return (ld)(B.x-a[1].x)*(A.y-a[1].y)<(ld)(B.y-a[1].y)*(A.x-a[1].x);
}
double semn(int i,int j,int k)
{
return (ld)(a[k].x-a[i].x)*(a[j].y-a[i].y)-(ld)(a[k].y-a[i].y)*(a[j].x-a[i].x);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lf%lf",&a[i].x,&a[i].y);
if(a[i].x<a[Min].x||a[i].x==a[Min].x&&a[i].y<a[Min].y)
{
Min=i;
}
}
swap(a[1],a[Min]);
sort(a+2,a+n+1,cmp);
st[1]=1;st[2]=2;st[top=3]=3;
for(i=4;i<=n;i++)
{
while(semn(st[top-1],st[top],i)>0)
--top;
st[++top]=i;
}
printf("%d\n",top);
for(i=1;i<=top;i++)
printf("%lf %lf\n",a[st[i]].x,a[st[i]].y);
return 0;
}