Pagini recente » Cod sursa (job #2693218) | Cod sursa (job #1155198) | Istoria paginii template/preoni-2007/footer | Cod sursa (job #1786894) | Cod sursa (job #2543141)
#include <cstdio>
#include <algorithm>
using namespace std;
struct coord {
double x, y;
};
int i, l, n;
coord v[120002], sts[120002], stt[12002];
void drp(double x, double y) {
double a, b;
int st=1;
if (x*(-v[0].y+v[n-1].y)-y*(v[n-1].x-v[0].x)+v[0].y*v[n-1].x-v[0].x*v[n-1].y<0) {
while (i>1 && st==1) {
a=x*(-stt[i-1].y+stt[i-2].y)-y*(stt[i-2].x-stt[i-1].x)+stt[i-2].x*stt[i-1].y-stt[i-1].x*stt[i-2].y;
st=0;
if (a>0) {
i--;
st=1;
}
}
stt[i].y=y;
stt[i].x=x;
i++;
}
if (x*(-v[0].y+v[n-1].y)-y*(v[n-1].x-v[0].x)+v[0].y*v[n-1].x-v[0].x*v[n-1].y>0) {
while (l>1 && st==1) {
a=x*(-sts[l-1].y+sts[l-2].y)-y*(sts[l-2].x-sts[l-1].x)+sts[l-2].x*sts[l-1].y-sts[l-1].x*sts[l-2].y;
st=0;
if (a<0) {
l--;
st=1;
}
}
sts[l].y=y;
sts[l].x=x;
l++;
}
b=x*(-v[0].y+v[n-1].y)-y*(v[n-1].x-v[0].x)+v[0].y*v[n-1].x-v[0].x*v[n-1].y;
a=x*(-stt[i-1].y+stt[i-2].y)-y*(stt[i-2].x-stt[i-1].x)+stt[i-2].x*stt[i-1].y-stt[i-1].x*stt[i-2].y;
printf("%lf %lf\n" ,b ,a);
}
bool cmp (coord a, coord b){
return a.y<b.y;
}
int main()
{
int k;
FILE *fin, *fout;
fin=fopen("infasuratoare.in" ,"r");
fout=fopen("infasuratoare.out" ,"w");
fscanf(fin, "%d" ,&n);
for(i=0;i<n;i++) {
fscanf(fin, "%lf%lf" ,&v[i].x ,&v[i].y);
v[i].x+=1000000000;
v[i].y+=1000000000;
}
sort(v, v+n, cmp);
sts[0].x=stt[0].x=v[0].x;
sts[0].y=stt[0].y=v[0].y;
sts[1].x=stt[1].x=v[1].x;
sts[1].y=stt[1].y=v[1].y;
i=l=2;
for(k=2;k<n;k++) {
drp(v[k].x, v[k].y);
}
fprintf(fout, "%d\n" ,i+l-1);
for (k=0;k<l;k++) {
fprintf(fout, "%.6lf %.6lf\n" ,sts[k].x-1000000000, sts[k].y-1000000000);
}
fprintf(fout, "%.6lf %.6lf\n" ,v[n-1].x-1000000000 ,v[n-1].y-1000000000);
for (k=i-2;k>0;k--) {
fprintf(fout, "%.6lf %.6lf\n" ,stt[k].x-1000000000, stt[k].y-1000000000);
}
return 0;
}