Pagini recente » Cod sursa (job #475950) | Cod sursa (job #98300) | Cod sursa (job #2892650) | Cod sursa (job #667358) | Cod sursa (job #3195708)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");
#define CW -1
#define COL 0
#define CCW 1
#define MAX_N 120000
struct pct
{
double x, y;
}v[MAX_N];
int n;
vector <pct> st;
double orientation(const pct& a, const pct& b, const pct& c) {
return (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
}
bool cmp(const pct& a, const pct& b)
{
return orientation(v[0], a, b) < 0;
}
void infasurareConvexa()
{
st.push_back(v[0]);
st.push_back(v[1]);
for(int i = 2; i < n; ++i)
{
while(st.size() >= 2 && orientation(st[st.size() - 2], st.back(), v[i]) >= 0)
{
st.pop_back();
}
st.push_back(v[i]);
}
}
int main()
{
double x, y;
in >> n;
for(int i = 0; i < n; ++i)
{
in >> x >> y;
v[i] = {x, y};
if(y > v[0].y)
{
swap(v[0], v[i]);
} else if(y == v[0].y && x > v[0].x)
{
swap(v[0], v[i]);
}
}
sort(v + 1, v + n, cmp);
infasurareConvexa();
out << st.size() << '\n';
out << setprecision(12) << fixed;
for(int i = 0; i < st.size(); ++i)
{
out << st[i].x << " " << st[i].y << '\n';
}
return 0;
}