Pagini recente » Cod sursa (job #904557) | Cod sursa (job #552889) | Cod sursa (job #1780092) | Cod sursa (job #2869816) | Cod sursa (job #1758656)
#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;
int err;
first.x = MAX_COORD;
first.y = MAX_COORD;
FILE *in = fopen("infasuratoare.in", "rt");
err = fscanf(in, "%ld\n", &nr_puncte);
for (i = 0; i < nr_puncte; i++) {
err = fscanf(in, "%lf %lf\n", &punct[i].x, &punct[i].y);
if (punct[i].x < first.x || (punct[i].x == first.x && punct[i].y < first.y)) {
first.x = punct[i].x;
first.y = punct[i].y;
i_first = i;
}
}
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) {
/*if ((p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x) < 0) {
return true;
}
return false;*/
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);
stack<coordonata> final;
final.push(punct[0]);
final.push(punct[1]);
coordonata aux1, aux2;
for (i = 2; i < nr_puncte; i++) {
while (true) {
aux1 = final.top();
final.pop();
aux2 = final.top();
if (unghi_polar(aux2, aux1, punct[i]) < 0) {
final.push(aux1);
final.push(punct[i]);
break;
}
}
}
FILE *out = fopen("infasuratoare.out", "wt");
fprintf(out, "%ud\n", final.size());
while (!final.empty()) {
first = final.top();
final.pop();
fprintf(out, "%lf %lf\n", first.x, first.y);
}
fclose(out);
//verificare();
return 0;
}