Pagini recente » Cod sursa (job #1634935) | Cod sursa (job #1320889) | Cod sursa (job #1140351) | Cod sursa (job #638689) | Cod sursa (job #3248151)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("gradina.in");
ofstream g("gradina.out");
const int NMAX = 250;
struct punct {
double x, y;
int parte;
} puncte[NMAX + 1], a, b, infas[NMAX + 1];
int Ion[NMAX + 1], Vasile[NMAX + 1], n, ci, cv, st[NMAX + 1];
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;
}
double 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
}
void infasuratoare(int v[NMAX + 1], int length)
{
int k=0, ck;
for (int i = 1; i<=length; ++i)
{
infas[i].x = puncte[v[i]].x;
infas[i].y = puncte[v[i]].y;
}
/*for (int i = 1; i<=length; ++i)
cout << infas[i].x << ' ' << infas[i].y << '\n';
cout << endl;*/
for (int i = 2; i<=length-1; ++i)
if (arie(infas[1], infas[length], infas[i]) < 0)
infas[i].parte = 1;
else
infas[i].parte = 2;
st[1] = 1;
k = 1;
for (int i = 1; i<=length; ++i)
{
if (infas[i].parte == 1)
///cout << puncte[st[i]].x << ' ' << puncte[st[i]].y << '\n';
}
cout << endl;
for (int i = 2; i<=length; ++i)
if (infas[i].parte == 1 || infas[i].parte == 0)
{
while (k>1 && arie(infas[st[k-1]], infas[st[k]], infas[i]) < 0)
--k;
st[++k] = i;
}
ck = k;
st[k] = length;
for (int i = length-1; i>=1; --i)
if (infas[i].parte == 2 || infas[i].parte == 0)
{
while (k>ck && arie(infas[st[k-1]], infas[st[k]], infas[i]) < 0)
--k;
st[++k] = i;
}
for (int i = 1; i<=k-1; ++i)
///cout << puncte[st[i]].x << ' ' << puncte[st[i]].y << '\n';
///cout << st[i] << ' ';
cout << endl;
}
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 = 1; i<=n; ++i)
cout << puncte[i].x << ' ' << puncte[i].y << endl;*/
for (int i = 1; i<=n; ++i)
for (int j = 1; j<=n; ++j)
{
if (i!=j)
{
a = puncte[i];
b = puncte[j];
ci = 0;
cv = 0;
for (int k = 1; k<=n; ++k)
{
if (arie(a, b, puncte[k]) < 0)
puncte[k].parte = 1;
else
puncte[k].parte = 2;
}
for (int k = 1; k<=n; ++k)
{
if (k == i)
Ion[++ci] = k;
else if (k == j)
Vasile[++cv] = k;
else
{
if (puncte[k].parte == 1)
Ion[++ci] = k;
else
Vasile[++cv] = k;
}
}
/*for (int i = 1; i<=ci; ++i)
cout << Ion[i] << ' ';
cout << endl;*/
infasuratoare(Ion, ci);
}
}
return 0;
}