Pagini recente » Cod sursa (job #46591) | Cod sursa (job #1796913) | Cod sursa (job #2058871) | Cod sursa (job #200443) | Cod sursa (job #2310848)
#include<stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef struct point{
double x;
double y;
double cos;
}point;
// Three points are a counter-clockwise turn if ccw > 0, clockwise if
// ccw < 0, and collinear if ccw = 0 because ccw is a determinant that
// gives twice the signed area of the triangle formed by p1, p2 and p3.
double ccw(point & p1, point & p2, point & p3){
return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
}
#define MAXN 120000
int N;
point P[MAXN];
int S[MAXN];
int lS;
bool sortByAngle(const point &lhs, const point &rhs) {
return lhs.cos > rhs.cos;
}
void complexhull(){
S[0]=0;
S[1]=1;
lS=2;
double sens;
for(int i=2; i<N ; i++){
while(lS>=2){
sens=ccw(P[S[lS-2]], P[S[lS-1]], P[i]);
if(sens <= 0){
// pop operation
lS--;
}
else
break;
}
S[lS]=i;
lS++;
}
}
int main(void){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N);
double x,y;
scanf("%lf %lf",&x,&y);
P[0].x=x; P[0].y=y;
double miny=y;
double minx=x;
int index=0;
for(int i=1;i<N;i++){
scanf("%lf %lf",&x,&y);
P[i].x=x; P[i].y=y;
if(y<miny){
miny=y;
minx=x;
index=i;
}
else{
if(y==miny && x<minx){
minx=x;
index=i;
}
}
}
point Q(P[0]);
P[0].x=P[index].x;
P[0].y=P[index].y;
P[index].x=Q.x;
P[index].y=Q.y;
double r;
for(int i=1;i<N;i++){
r=(P[i].x-P[0].x)*(P[i].x-P[0].x);
r+=(P[i].y-P[0].y)*(P[i].y-P[0].y);
r=sqrt(r);
P[i].cos=(P[i].x-P[0].x)/r;
}
sort(P + 1, P + N, sortByAngle);
complexhull();
printf("%d\n",lS);
for(int i=0;i<lS;i++){
printf("%lf %lf\n",P[S[i]].x,P[S[i]].y);
}
return 0;
}