Pagini recente » Cod sursa (job #2333253) | Cod sursa (job #437179) | Cod sursa (job #1913184) | Cod sursa (job #2491778) | Cod sursa (job #418458)
Cod sursa(job #418458)
#include<stdio.h>
#include<algorithm>
using namespace std;
#define N 120100
int stiva[N],K;
char fol[N];
struct punct{
double x,y;
}pct[N];
struct cmp{
bool operator()(const punct a,const punct b)const{
if(a.x<b.x)
return true;
if(a.x==b.x)
if(a.y<b.y)
return true;
return false;
}
};
float semn(punct a,punct b,punct c){
return (a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y));
}
void solve(int n){
int i;
K=1;
fol[0]=1;
for(i=1;i<n;++i){
while(K>1 && semn(pct[stiva[K-1]],pct[stiva[K]],pct[i])<0)
fol[stiva[K--]]=0;
if(K==1){
stiva[++K]=i;
fol[i]=1;
continue;
}
if(semn(pct[stiva[K-1]],pct[stiva[K]],pct[i])>0){
stiva[++K]=i;
fol[i]=1;
}
}
for(i=n-1;i>=0;--i){
if(!fol[i] || !i){
while(K>1 && semn(pct[stiva[K-1]],pct[stiva[K]],pct[i])<0)
fol[stiva[K--]]=0;
if(K==1){
stiva[++K]=i;
fol[i]=1;
}
if(semn(pct[stiva[K-1]],pct[stiva[K]],pct[i])>0){
stiva[++K]=i;
fol[i]=1;
}
}
}
printf("%d\n",K-1);
for(i=1;i<K;++i)
printf("%lf %lf\n",pct[stiva[i]].x,pct[stiva[i]].y);
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n,i;
scanf("%d",&n);
for(i=0;i<n;++i)
scanf("%lf%lf",&pct[i].x,&pct[i].y);
sort(pct,pct+n,cmp());
solve(n);
fclose(stdin);
fclose(stdout);
return 0;
}