Pagini recente » Cod sursa (job #904297) | Cod sursa (job #1256513) | Cod sursa (job #647365) | Cod sursa (job #2116267) | Cod sursa (job #1704293)
#include <bits/stdc++.h>
using namespace std;
const double eps = 1.e-12;
struct POINT {
double x, y;
} c;
bool cmp(POINT a, POINT b) {
double an, bn;
if(abs(a.x-c.x)<eps)
an = 1.e12;
else
an = (a.y-c.y)/(a.x-c.x);
if(abs(b.x-c.x)<eps)
bn = 1.e12;
else
bn = (b.y-c.y)/(b.x-c.x);
return bn > an;
}
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;
}
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 = v[0];
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 = v[i];
c_index = i;
}
else if(abs(c.x-v[i].x)<eps && c.y-eps>=v[i].y) {
c = v[i];
c_index = i;
}
}
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;
}