Pagini recente » Cod sursa (job #1880876) | Cod sursa (job #1001502) | Cod sursa (job #1045302) | Cod sursa (job #829743) | Cod sursa (job #416025)
Cod sursa(job #416025)
#include <cstdio>
#include <algorithm>
#include <math.h>
#define NMAX 100000
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)
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);
/*
if (a.x == b.x)
return a.y < b.y;
return a.x < b.x;
*/
}
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--;
rez[++rC] = p[i];
}
}
int main(){
readPoints();
grahamScan();
for (int i=0; i<n; i++)
printf("%lf %lf\n", p[i].x, p[i].y);
writePoints();
//getchar();
return 0;
}