Pagini recente » Cod sursa (job #2988226) | Cod sursa (job #1227735) | Cod sursa (job #2623192) | Cod sursa (job #1889714) | Cod sursa (job #1934800)
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
#include <iomanip>
#define NMAX 120010
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x, y;
friend bool operator < (punct a, punct b);
};
int n;
punct p, v[NMAX];
stack<punct> S;
vector<punct> sol;
bool operator < (punct a, punct b)
{
return (a.y - p.y) * (b.x - p.x) < (a.x - p.x) * (b.y - p.y) ||
((a.y - p.y) * (b.x - p.x) == (a.x - p.x) * (b.y - p.y) &&
(a.x - p.x) * (a.x - p.x) + (a.y - p.y) * (a.y - p.y) < (b.x - p.x) * (b.x - p.x) + (b.y - p.y) * (b.y - p.y));
}
void citire();
double arie(punct a, punct b, punct c);
int main()
{
int i;
citire();
sort(v, v + n);
S.push(v[0]);
for (i = 1; i < n; i++)
{
//analizez vf stivei cu v[i] si v[i + 1]
if (arie(S.top(), v[i], v[i + 1]) <= 0)
{
while (!S.empty())
{
v[i] = S.top();
S.pop();
if (arie(S.top(), v[i], v[i + 1]) > 0)
break;
}
}
S.push(v[i]);
}
//afisare invers
while (!S.empty())
{
sol.push_back(S.top());
S.pop();
}
fout << sol.size() << '\n';
fout << fixed << setprecision(13);
for (i = sol.size() - 1; i >= 0; i--)
fout << sol[i].x << ' ' << sol[i].y << '\n';
fout.close();
return 0;
}
void citire()
{
int i;
fin >> n;
fin >> v[0].x >> v[0].y;
p = v[0];
for (i = 1; i < n; i++)
{
fin >> v[i].x >> v[i].y;
if (v[i].x < p.x || (v[i].x == p.x && v[i].y < p.y))
p = v[i];
}
//v[n] = v[0];
}
double arie(punct a, punct b, punct c)
{
return (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) / 2;
}