Pagini recente » Cod sursa (job #1893591) | Cod sursa (job #2279728) | Cod sursa (job #251269)
Cod sursa(job #251269)
#include<cstdio>
#include<algorithm>
using namespace std;
struct Punct {
double x, y;
}a[120009];
int Stiva[120009],vf=-1;
bool viz[120009];
int cmp(Punct a, Punct b){
if(a.y==b.y)
return a.x<b.x;
return a.y<b.y;
}
void coeficienti(Punct a, Punct b, double& aa, double& bb, double& cc){
aa=a.y-b.y;
bb=b.x-a.x;
cc=b.y*a.x-b.x*a.y;
}
char semn(int gh){
double aa, bb, cc;
coeficienti(a[Stiva[vf-1]], a[Stiva[vf]], aa, bb, cc);
if(aa*a[gh].x+bb*a[gh].y+cc>=0)
return '+';
return '-';
}
int main(){
int i, n;
freopen("infasuratoare.in","r",stdin);
scanf("%d", &n);
for(i=0;i<n;i++)
scanf("%lf%lf",&(a[i].x), &(a[i].y));
sort(a, a+n, cmp);
Stiva[++vf]=0;
Stiva[++vf]=1;
viz[0]=1;
viz[1]=1;
for(i=2;i<n&&a[i].y>=a[i-1].y;i++){
while(vf>0&&semn(i)=='-') viz[Stiva[vf--]]=0;
viz[Stiva[++vf]=i]=1;
}
for(i=n-1;i>=0;i--)
if(!viz[i]){
while(vf>0&&semn(i)=='-') viz[Stiva[vf--]]=0;
viz[Stiva[++vf]=i]=1;
}
while(semn(0)=='-') --vf;
freopen("infasuratoare.out","w",stdout);
printf("%d\n",vf+1);
for(i=0;i<=vf;i++){
printf("%.6lf ",a[Stiva[i]].x);
printf("%.6lf\n",a[Stiva[i]].y);
}
return 0;
}