Pagini recente » Istoria paginii utilizator/suki | Monitorul de evaluare | Istoria paginii utilizator/florinhaja | Diferente pentru utilizator/deehoroejkoli intre reviziile 117 si 116 | Cod sursa (job #1029076)
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <iomanip>
std::ifstream f("infasuratoare.in");
std::ofstream g("infasuratoare.out");
int n;
typedef struct punct
{
double x;
double y;
bool operator <(const punct& p) const
{
return (x < p.x || (x == p.x && y < p.y) );
}
} punct_obj;
punct *punctXY;
/// | x1 y1 1 |
/// det = | x2 y2 1 |
/// | x3 y3 1 |
/// daca det < 0 => P3(x3, y3) in dreapta (jos) vectorului P1P2
/// daca det > 0 => P3(x3, y3) in stanga (sus) vectorului P1P2
double det (punct pct1, punct pct2, punct pct3)
{
return (pct1.x*pct2.y + pct2.x*pct3.y + pct3.x*pct1.y
- pct3.x*pct2.y - pct1.x*pct3.y - pct2.x*pct1.y);
}
int main ()
{
f >> n;
punctXY = new punct[n];
f >> punctXY[0].x >> punctXY[0].y;
int maxX = punctXY[0].x ,minX = punctXY[0].x;
int indiceMax = 0, indiceMin = 0;
/// 1. determina punctele de extrem dupa x (abscisa minima si maxima)
/// P_min : x = minX, indice = indiceMin; P_max : x = maxX, indice = indiceMax
for (int i = 1; i < n; ++ i)
{
f >> punctXY[i].x >> punctXY[i].y;
if (punctXY[i].x < minX)
{
minX = punctXY[i].x;
indiceMin = i;
}
else
if (punctXY[i].x > maxX)
{
maxX = punctXY[i].x;
indiceMax = i;
}
}
/// 2. separa multimea S in S_inf (stanga) si S_sup (dreapta)
std::vector <punct> sInf;
std::vector <punct> sSup;
sInf.push_back(punctXY[indiceMin]);
sSup.push_back(punctXY[indiceMin]);
for (int i = 0; i < n; ++ i)
if (i != indiceMax && i != indiceMin)
{
if (det(punctXY[indiceMin], punctXY[indiceMax], punctXY[i]) < 0)
{
sInf.push_back(punctXY[i]);
}
else
{
sSup.push_back(punctXY[i]);
}
}
sInf.push_back(punctXY[indiceMax]);
sSup.push_back(punctXY[indiceMax]);
/// 3. sorteaza S_inf si S_sup (sort din STL)
std::sort(sInf.begin() + 1, sInf.end() - 1);
std::sort(sSup.begin() + 1, sSup.end() - 1);
/// 4. creeaza infasuratoarea convexa pentru S_inf si S_sup
int i = 0;
/// 4.1. infasuratoare convexa pentru s_sup
while (i + 2 < sSup.size())
{
if (det (sSup[i], sSup[i + 2], sSup[i + 1]) > 0)
++ i;
else
sSup.erase(sSup.begin() + i + 1);
}
i = 0;
/// 4.2. infasuratoare convexa pentru s_inf
indiceMin = 0;
punct p = sInf[0];
if (sInf[sInf.size() - 1].y < p.y || sInf[sInf.size() - 1].y == p.y && sInf[sInf.size() - 1].x < p.x)
{
p = sInf[sInf.size() - 1];
indiceMin = sInf.size() - 1;
}
while (i + 2 < sInf.size())
{
if (det (sInf[i], sInf[i + 2], sInf[i + 1]) < 0)
{
++ i;
if (sInf[i].y < p.y || sInf[i].y == p.y && sInf[i].x < p.x)
{
p = sInf[i];
indiceMin = i;
}
}
else
sInf.erase(sInf.begin() + i + 1);
}
/// 5. afiseaza in sens trigonometric punctele din infasuratoarea convexa
g << sInf.size() + sSup.size() - 2 << "\n";
for (int i = indiceMin; i < sInf.size(); ++ i)
g << std::fixed << std::setprecision(6) << sInf[i].x << " " << sInf[i].y << "\n";
for (int i = sSup.size() - 2; i > 0; -- i)
g << std::fixed << std::setprecision(6) << sSup[i].x << " " << sSup[i].y << "\n";
for (int i = 0; i < indiceMin; ++ i)
g << std::fixed << std::setprecision(6) << sInf[i].x << " " << sInf[i].y << "\n";
return 0;
}