Pagini recente » Cod sursa (job #2526242) | Cod sursa (job #1397812) | Cod sursa (job #2032908) | Cod sursa (job #2746915) | Cod sursa (job #2806130)
#include <stdio.h>
#include <algorithm>
#include <bitset>
using namespace std;
FILE* f, * g;
///sens trigonometric=sens antiorar
struct point
{
double x, y;
}v[120002];
int s[120002];
int n, top;
bitset <120002>yes;
bool how(point a, point b)
{
if (a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
void read()
{
fscanf(f, "%d", &n);
for (int i = 1;i <= n;++i)
fscanf(f, "%lf %lf", &v[i].x, &v[i].y);
sort(v + 1, v + n + 1, how);
}
///diferenta vectorilor p1p2 si p2p3
///daca e 0 punctele sunt coliniare
///<0 (punctele constituie o orientare in sensul invers acelor de ceasornic),
///>0 (in sensul acelor de ceasornic)
double scanareGhram(point a, point b, point c)
{
return ((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x));
}
void solve()
{
int ok = 1;
s[++top] = 1;
s[++top] = 2, yes[2] = 1;
int i = 3;///indicele punctului care urmeaza sa fie verificat pentru a stabili daca se afla pe infasuratoare
while (!yes[1])///nu s-a realizat cel mai optim poligon
{
while (yes[i])
{
if (i == n) ok = -1;
i += ok;
}
while (top >= 2 && scanareGhram(v[s[top - 1]], v[s[top]], v[i]) > 0)
yes[s[top]] = 0, --top;
s[++top] = i, yes[i] = 1;
}
}
void write()
{
fprintf(g, "%d\n", top - 1);
for (int i = top - 1;i >= 1;--i)
fprintf(g, "%lf %lf\n", v[s[i]].x, v[s[i]].y);
}
int main()
{
f = fopen("infasuratoare.in", "r");
g = fopen("infasuratoare.out", "w");
read();
solve();
write();
fclose(f);
fclose(g);
return 0;
}