Pagini recente » Cod sursa (job #1535885) | Cod sursa (job #2936058) | Cod sursa (job #415330) | Cod sursa (job #2920354) | Cod sursa (job #1758658)
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stack>
using namespace std;
#define MAX_NR_PUNCTE 120000
#define MAX_COORD 1000000000.0
typedef struct {
double x;
double y;
} coordonata;
long nr_puncte;
coordonata punct[MAX_NR_PUNCTE];
coordonata first;
long i_first;
void swap_punct(coordonata *p1, coordonata *p2) {
coordonata aux;
aux = *p1;
*p1 = *p2;
*p2 = aux;
}
void citire() {
long i;
first.x = MAX_COORD;
first.y = MAX_COORD;
FILE *in = fopen("infasuratoare.in", "rt");
fscanf(in, "%ld\n", &nr_puncte);
for (i = 0; i < nr_puncte; i++) {
fscanf(in, "%lf %lf\n", &punct[i].x, &punct[i].y);
if (punct[i].x < first.x) {
first = punct[i];
i_first = i;
} else if (punct[i].x == first.x && punct[i].y < first.y) {
}
}
fclose(in);
swap_punct(&punct[0], &punct[i_first]);
}
bool comp_first(coordonata c1, coordonata c2) {
double m1 = (c1.y - first.y) / (c1.x - first.x);
double m2 = (c2.y - first.y) / (c2.x - first.x);
return m1 > m2;
}
void verificare() {
printf("-----VERIFICARE-----\n");
for (long i = 0; i < nr_puncte; i++) {
printf("x %lf y %lf\n", punct[i].x, punct[i].y);
}
printf("first: x %lf y %lf\n", first.x, first.y);
}
double unghi_polar(coordonata p1, coordonata p2, coordonata p3) {
return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}
int main()
{
long i;
citire();
sort(punct + 1, punct + nr_puncte, comp_first);
coordonata final[MAX_NR_PUNCTE];
long final_size = 2;
final[0] = punct[0];
final[1] = punct[1];
for (i = 2; i < nr_puncte; i++) {
while (true) {
if (unghi_polar(final[final_size - 2], final[final_size - 1], punct[i]) < 0) {
final[final_size++] = punct[i];
break;
} else {
final_size--;
}
}
}
FILE *out = fopen("infasuratoare.out", "wt");
fprintf(out, "%u\n", final_size);
for (i = 0; i < final_size; i++) {
fprintf(out, "%lf %lf\n", final[i].x, final[i].y);
}
fclose(out);
//verificare();
return 0;
}