Pagini recente » Cod sursa (job #2785643) | Cod sursa (job #1617263) | Cod sursa (job #1191106) | Cod sursa (job #957592) | Cod sursa (job #2158314)
#include <algorithm>
#include <cstdio>
typedef double field;
#define zero ((field)0)
typedef struct point {field x, y;} point;
bool susjosstangadreapta(point a, point b) {
return (a.y == b.y) ? (a.x < b.x) : (a.y < b.y);
}
typedef enum relpos {LEFT = 1, RIGHT = -1, ON = 0} relpos;
relpos unde(point a, point b, point c) {
field det = a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
if(det < zero) return RIGHT;
if(det > zero) return LEFT;
return ON;
}
point points[120000];
int stiva[120001], h=-1;
inline void baga_punct(int i) {
relpos in_care_semiplan = unde(points[stiva[h-1]], points[stiva[h]], points[i]);
if(in_care_semiplan == LEFT)
stiva[++h] = i;
if(in_care_semiplan == RIGHT) {
while(in_care_semiplan == RIGHT && --h > 1)
in_care_semiplan = unde(points[stiva[h-1]], points[stiva[h]], points[i]);
stiva[++h] = i;
}
}
int main() {
int n, i;
FILE *fin = fopen("infasuratoare.in", "r");
fscanf(fin, "%d", &n);
for(i=0; i<n; i++)
fscanf(fin, "%lf%lf", &points[i].x, &points[i].y);
fclose(fin);
std::sort(points, points+n, susjosstangadreapta);
stiva[++h] = 0;
stiva[++h] = 1;
for(i=2; i <= n-1; i++) baga_punct(i);
for(i=n-2; i >= 1; i--) baga_punct(i);
FILE *fout = fopen("infasuratoare.out", "w");
fprintf(fout, "%d\n", h+1);
for(i=0; i<=h; i++) {
fprintf(fout, "%.6lf %.6lf\n", points[stiva[i]].x, points[stiva[i]].y);
}
fclose(fout);
return 0;
}