Pagini recente » Cod sursa (job #242630) | Cod sursa (job #2697018) | Cod sursa (job #2529950) | Cod sursa (job #574913) | Cod sursa (job #3186228)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
struct nume
{
double x, y;
};
nume v[120001];
double minx = 1e9, miny = 1e9;
vector <nume>st;
bool comp(nume a, nume b)
{
return (-minx + a.x) * (-miny + b.y) > (-miny + a.y) * (-minx + b.x);
}
double determinant(nume a, nume b)
{
return a.x * b.y - a.y * b.x;
}
int orientare(nume a, nume b, nume c)
{
double val = determinant(a, b) + determinant(b, c) + determinant(c, a);
if(val > 0)
return 1;
else
if(val == 0)
return 2;
else
return 3;
}
int main()
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
double x, y;
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> v[i].x >> v[i].y;
if(v[i].y < miny)
{
miny = v[i].y;
minx = v[i].x;
swap(v[1], v[i]);
}
}
sort(v + 2, v + n + 1, comp);
st.push_back(v[1]);
st.push_back(v[2]);
for(int i = 3; i <= n; i++)
{
while(st.size() > 1 && orientare(st[st.size() - 2], st[st.size() - 1], v[i]) != 1)
st.pop_back();
st.push_back(v[i]);
}
cout << st.size() << '\n';
for(int i = 0; i < st.size(); i++)
{
cout << fixed << setprecision(6) << st[i].x << ' ' << st[i].y << '\n';
}
return 0;
}