Pagini recente » Cod sursa (job #3325522) | Cod sursa (job #139935) | Cod sursa (job #445814) | Cod sursa (job #295010) | Cod sursa (job #3309761)
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>
using namespace std;
struct point
{
double x;
double y;
};
point a[120001]; //a[0] is the point we start with
stack<point> ans;
stack<point> aux;
double det(point a, point b, point c)
{
double res = a.x * b.y + b.x * c.y + c.x * a.y;
return res - a.y * b.x - b.y * c.x - c.y * a.x;
}
bool comp(point n, point m)
{
double res = det(a[0], n, m);
if (res > 0) {return 1;}
if (res < 0) {return 0;}
return n.x < m.x;
}
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n = 0;
point last;
fin >> n >> a[0].x >> a[0].y;
for (int i = 1; i < n; i++)
{
fin >> a[i].x >> a[i].y;
if (a[i].x < a[0].x || (a[i].x == a[0].x && a[i].y < a[0].y))
{
swap(a[0], a[i]);
}
}
a[n] = a[0]; //so it makes the full polygon
sort(a + 1, a + n, comp);
ans.push(a[0]);
for (int i = 1; i <= n; i++)
{
while (ans.size() >= 2)
{
last = ans.top();
ans.pop();
if (det(ans.top(), last, a[i]) > 0) {ans.push(last); break;}
}
ans.push(a[i]);
}
while (!ans.empty())
{
aux.push(ans.top());
ans.pop();
}
fout << aux.size() << '\n';
aux.pop();
while (!aux.empty())
{
fout << setprecision(8) << fixed << aux.top().x << ' ' << aux.top().y << '\n';
aux.pop();
}
}