Pagini recente » Cod sursa (job #2594630) | Cod sursa (job #800204)
Cod sursa(job #800204)
#include <cstdio>
#include <vector>
#include <algorithm>
#define NMAX 120001
#define VMAX 1000000001
using namespace std;
FILE *inFile = fopen ("infasuratoare.in", "r");
FILE *outFile = fopen ("infasuratoare.out", "w");
struct punct
{
double x;
double y;
double p;
} p[NMAX];
vector <punct> C;
int n;
bool cmp(punct a, punct b)
{
if (a.p < b.p)
return 1;
return 0;
}
void read()
{
int poz;
int xmin = VMAX;
int ymin = VMAX;
fscanf (inFile, "%d\n", &n);
for (int i = 0; i < n; ++ i)
{
fscanf (inFile, "%lf %lf\n", &p[i].x, &p[i].y);
if (p[i].x < xmin || p[i].x == xmin && p[i].y < ymin)
{
poz = i;
xmin = p[i].x;
ymin = p[i].y;
}
}
swap (p[poz], p[n - 1]);
-- n;
}
void panta()
{
for (int i = 0; i < n; ++ i)
{
if (p[i].x != p[n].x)
p[i].p = (p[i].y - p[n].y) / (p[i].x - p[n].x);
else
p[i].p = VMAX;
}
sort (p, p + n, cmp);
}
double determinant(punct a, punct b, punct c)
{
return a.x * b.y + a.y * c.x + b.x * c.y - b.y * c.x - a.y * b.x - a.x * c.y;
}
void infasuratoare()
{
C.push_back(p[n]);
C.push_back(p[0]);
for (int i = 1; i < n; ++ i)
{
int m = C.size() - 1;
if (determinant(C[m - 1], C[m], p[i]) >= 0)
C.push_back(p[i]);
else
{
while (determinant(C[m - 1], C[m], p[i]) < 0)
{
C.pop_back();
-- m;
}
C.push_back(p[i]);
}
}
}
void write()
{
fprintf (outFile, "%d\n", C.size());
for (unsigned int i = 0; i < C.size(); ++ i)
fprintf (outFile, "%.6lf %.6lf\n", C[i].x, C[i].y);
}
int main()
{
read();
panta();
infasuratoare();
write();
return 0;
}