Pagini recente » Cod sursa (job #360941) | Cod sursa (job #1960269) | Cod sursa (job #1724947) | Cod sursa (job #564087) | Cod sursa (job #1704331)
#include <bits/stdc++.h>
using namespace std;
const double eps = 1.e-12;
struct POINT {
double x, y;
} c;
int sccw(POINT a, POINT b, POINT c) {
double s = (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
if(abs(s) < eps)
return 0;
if(s>=eps)
return 1;
else
return -1;
}
bool cmp(POINT a, POINT b) {
return sccw(c, a, b) >= 1;
}
POINT v[120005],
cvc[120005];
int main(void) {
FILE *fi = fopen("infasuratoare.in", "r");
FILE *fo = fopen("infasuratoare.out", "w");
int n, c_index, c_top;
fscanf(fi,"%d",&n);
fscanf(fi,"%lf%lf",&v[0].x,&v[0].y);
c_index = 0;
for(int i=1; i<n; ++i) {
fscanf(fi,"%lf%lf",&v[i].x,&v[i].y);
if(c.x-eps>=v[i].x)
c_index = i;
else if(abs(c.x-v[i].x)<eps && c.y-eps>=v[i].y)
c_index = i;
}
c = v[c_index];
swap(v[0], v[c_index]);
sort(v+1,v+n,cmp);
cvc[0] = c;
cvc[1] = v[1];
c_top = 1;
for(int i=2; i<n; ++i) {
if(i==c_index)
continue;
while(c_top && sccw(cvc[c_top-1], cvc[c_top], v[i])<0)
--c_top;
cvc[++c_top] = v[i];
}
fprintf(fo,"%d\n",++c_top);
for(int i=0; i<c_top; ++i)
fprintf(fo,"%f %f\n",cvc[i].x,cvc[i].y);
fclose(fi);
fclose(fo);
return 0;
}