Cod sursa(job #416113)
#include <cstdio>
#include <algorithm>
#include <math.h>
#define NMAX 120010
typedef struct{
double x, y;
}point;
point p[NMAX], rez[NMAX];
int n, rC;
void readPoints(){
FILE* f = fopen("infasuratoare.in","r");
fscanf(f, "%d", &n);
int min = 0;
for (int i = 0; i < n; i++){
fscanf(f,"%lf %lf", &p[i].x, &p[i].y);
if (p[i].y < p[min].y || p[i].y == p[min].y && p[i].x < p[i].y)
min = i;
}
point aux = p[min];
p[min] = p[0];
p[0] = aux;
}
void writePoints(){
freopen("infasuratoare.out", "w", stdout);
printf("%d\n", rC);
for (int i = 1; i<=rC; i++)
printf("%lf %lf\n", rez[i].x, rez[i].y);
}
int operator<(point a, point b){
//return atan2(a.y - p[0].y, a.x - p[0].x) < atan2(b.y - p[0].y, b.x - p[0].x);
return (a.x-p[0].x)*(b.y-p[0].y) - (a.y-p[0].y)*(b.x-p[0].x)>0;
}
int ccw(point p1, point p2, point p3){
return (int)((p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x));
}
void grahamScan(){
// sort by X and then by Y
std::sort(p+1, p+n);
p[n] = p[0];
rC = 0;
rez[++rC] = p[0];
rez[++rC] = p[1];
for (int i = 2; i<n; i++){
while (ccw(rez[rC-1], rez[rC], p[i]) <= 0 && rC > 2)
rC--;
rez[++rC] = p[i];
}
}
int main(int argc, char* argv[]){
readPoints();
grahamScan();
for (int i=0; i<n; i++)
printf("%lf %lf\n", p[i].x, p[i].y);
writePoints();
//getchar();
return 0;
}