Pagini recente » Cod sursa (job #509973) | Cod sursa (job #1717536) | Cod sursa (job #1001525) | Cod sursa (job #232316) | Cod sursa (job #2019713)
#include<cstdio>
#include<algorithm>
using namespace std;
const int NMAX=120005;
const double eps=1.0e-14;
struct POINT{
double x,y;
}p[NMAX];
int h[NMAX];
double dist(POINT p1, POINT p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double CrossProduct(POINT a, POINT b, POINT c){
return (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
}
int CounterClockWise(POINT a, POINT b, POINT c){
double cp=CrossProduct(a, b, c);
if(fabs(cp)<eps)
return 0;
if(cp>=eps)
return 1;
return -1;
}
bool cmp(POINT p1, POINT p2){
int c=CounterClockWise(p[0], p1, p2);
if(c==1)
return 1;
if(c==-1)
return 0;
double d1=dist(p[0], p1);
double d2=dist(p[0], p2);
if(d1-d2<=eps)
return 1;
return 0;
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int top,n,ll=-1;
double minx=1000000005,miny=1000000005;
scanf("%d", &n);
for(int i=0;i<n;i++){
scanf("%lf%lf", &p[i].x, &p[i].y);
if(miny-p[i].y>=eps){
minx=p[i].x;
miny=p[i].y;
ll=i;
}
else
if(fabs(p[i].y-miny)<eps && minx-p[i].x>=eps){
ll=i;
minx=p[i].x;
}
}
p[0]=p[ll];
sort(p+1, p+n, cmp);
p[n]=p[0];
h[1]=top=1;
int i=2;
while(i<=n)
if(CounterClockWise(p[h[top-1]], p[h[top]], p[i])>0){
h[++top]=i;
i++;
}
else
top--;
printf("%d\n", top);
for(int i=0;i<top;i++)
printf("%f %f\n", p[h[i]].x, p[h[i]].y);
return 0;
}