Pagini recente » Cod sursa (job #522839) | Cod sursa (job #1414128) | Cod sursa (job #474233) | Cod sursa (job #2408613) | Cod sursa (job #3246389)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int NMAX = 120000;
struct punct {
float x, y;
} puncte[NMAX + 1], jos[NMAX + 1], sus[NMAX + 1], st1[NMAX + 1], st2[NMAX + 1];
int n, kj, ks, k1, k2;
void afis(punct v[NMAX + 1], int length)
{
for (int i = 1; i<=length; ++i)
g << v[i].x << ' ' << v[i].y << '\n';
}
bool cmp(punct P1, punct P2)
{
if (P1.x > P2.x)
return false;
if (P1.x == P2.x)
if (P1.y > P2.y)
return false;
return true;
}
float arie (punct P1, punct P2, punct P3)
{
return (P1.x*P2.y + P2.x*P3.y + P3.x*P1.y - P2.y*P3.x - P3.y*P1.x - P1.y*P2.x); /// daca <0 => P3 e sub semiplan
/// daca >0 => P3 e peste semiplan
}
int valid(int e, int sgn)
{
if (sgn == -1)
return e<0;
else
return e>0;
}
void solve(punct v[NMAX + 1], int length, punct st[NMAX + 1], int &k, int sgn)
{
if (sgn == -1)
{
st[++k] = v[1];
for (int i = 2; i <= length; ++i)
{
while ( k>1 && valid(arie(st[k-1], st[k], v[i]), sgn))
--k;
st[++k] = v[i];
}
}
else
{
st[++k] = v[length];
for (int i = length-1; i >=1 ; --i)
{
while ( k>1 && !valid(arie(st[k-1], st[k], v[i]), sgn))
--k;
st[++k] = v[i];
}
}
}
int main()
{
f >> n;
for (int i = 1; i<=n; ++i)
f >> puncte[i].x >> puncte[i].y;
sort(puncte + 1, puncte + n + 1, cmp);
for (int i = 2; i<=n-1; ++i)
if (arie(puncte[1], puncte[n], puncte[i]) < 0)
jos[++kj] = puncte[i];
else
if (arie(puncte[1], puncte[n], puncte[i]) > 0)
sus[++ks] = puncte[i];
st1[++k1] = puncte[1];
solve(jos,kj, st1, k1, -1);
st2[++k2] = puncte[n];
solve(sus, ks, st2, k2, 1);
g << k1+k2 << '\n';
afis(st1, k1);
afis(st2, k2);
///afis(puncte, n);
return 0;
}