Pagini recente » Cod sursa (job #1582716) | Cod sursa (job #1409816) | Cod sursa (job #1876119) | Cod sursa (job #1234418) | Cod sursa (job #1807359)
#include <cstdio>
#include <algorithm>
#define NMAX 120010
using namespace std;
struct pct {
double x, y;
};
pct P[NMAX], S[NMAX];
int vfS, n;
void citire();
void Graham();
inline bool cmp(const pct&, const pct&);
inline double crossProduct(const pct&, const pct&, const pct&);
void afisare();
int main() {
citire();
Graham();
afisare();
return 0;
}
void citire() {
FILE*fin = fopen("infasuratoare.in", "r");
fscanf(fin, "%d", &n);
unsigned int i;
for (i = 1; i <= n; ++i)
fscanf(fin, "%lf %lf", &P[i].x, &P[i].y);
fclose(fin);
return;
}
void Graham() {
unsigned int bottomLeftPoint = 1;
for (i = 2; i <= n; ++i)
if (P[i].y<P[bottomLeftPoint].y || (P[i].y == P[bottomLeftPoint].y && P[i].x<P[bottomLeftPoint].x)) {
bottomLeftPoint = i;
}
swap (P[bottomLeftPoint], P[1]);
sort (P + 2, P + n + 1, cmp);
S[1] = P[1]; S[2] = P[2]; vfS = 2;
unsigned int i;
for (i = 3; i <= n; ++i) {
while (vfS>1 && crossProduct(S[vfS - 1], S[vfS], P[i]) <= 0)
--vfS;
S[++vfS] = P[i];
}
return;
}
inline double crossProduct(const pct &a, const pct &b, const pct &c) {
return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
}
inline bool cmp(const pct &a, const pct &b) {
return crossProduct(P[1], a, b)>0;
}
void afisare() {
FILE*fout = fopen("infasuratoare.out", "w");
fprintf(fout, "%d\n", vfS);
unsigned int i;
for (i = 1; i <= vfS; ++i)
fprintf(fout, "%f %f\n", S[i].x, S[i].y);
fclose(fout);
return;
}