Pagini recente » Cod sursa (job #1235608) | Cod sursa (job #2536156) | Cod sursa (job #790213) | Cod sursa (job #729340) | Cod sursa (job #1476143)
#include <stdio.h>
#define nmax 120010
using namespace std;
struct date { double x,y; };
int n,i,j,stiva[nmax],head=0;
bool fr[nmax];
date t[nmax];
double upper_line(date a,date b,date c)
{
return (a.x*b.y+a.y*c.x+b.x*c.y-c.x*b.y-a.y*b.x-c.y*a.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",&t[i].x,&t[i].y);
stiva[1]=1; stiva[2]=2; head=2; fr[2]=true;
for (i=3;i<=n;i++) {
if (fr[i]) continue;
while (head>=2 && upper_line(t[stiva[head-1]],t[stiva[head]],t[i])<=0)
fr[stiva[head]]=false,head--;
head++; stiva[head]=i; fr[i]=true;
}
for (i=n-1;i>=1;i--) {
if (fr[i]) continue;
while (head>=2 && upper_line(t[stiva[head-1]],t[stiva[head]],t[i])<=0)
fr[stiva[head]]=false,head--;
head++; stiva[head]=i; fr[i]=true;
}
head--;
printf("%d\n",head);
for (i=1;i<=head;i++) printf("%lf %lf\n",t[stiva[i]].x,t[stiva[i]].y);
return 0;
}