Pagini recente » Cod sursa (job #1366094) | Cod sursa (job #41175) | STL_MAN | Cod sursa (job #2793578) | Cod sursa (job #2535737)
#include <cstdio>
#include <algorithm>
#define LengthMax 128000
using namespace std;
struct Point {
double x,y;
};
int pointsLength,solLength;
Point points[LengthMax],sol[LengthMax];
void scanPt(Point&P) {
scanf("%lf%lf",&P.x,&P.y);
}
void read() {
int i;
scanf("%d",&pointsLength);
for(i=0;i<pointsLength;++i) {
scanPt(points[i]);
}
}
bool pointsCmp(Point P1,Point P2) {
if(P1.x==P2.x) {
return P1.y<P2.y;
}
else {
return P1.x<P2.x;
}
}
void addInSol(Point P) {
sol[solLength++]=P;
}
char trigo(Point P1,Point P2,Point P3) {
return ((P1.x-P3.x)*(P2.y-P3.y)-(P2.x-P3.x)*(P1.y-P3.y))>=0;
}
void ver() {
for(;solLength>2;) {
if(!trigo(sol[solLength-3],sol[solLength-2],sol[solLength-1])) {
--solLength;
sol[solLength-1]=sol[solLength];
}
else {
break;
}
}
}
void hull() {
int i;
addInSol(points[0]);
for(i=1;i<pointsLength;++i) {
addInSol(points[i]);
ver();
}
for(i=pointsLength-2;i>=0;--i) {
addInSol(points[i]);
ver();
}
}
void printPt(Point P) {
printf("%.6f %.6f\n",P.x,P.y);
}
void display() {
int i;
--solLength;
printf("%d\n",solLength);
for(i=0;i<solLength;++i) {
printPt(sol[i]);
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
read();
sort(points,points+pointsLength,pointsCmp);
hull();
display();
return 0;
}