Pagini recente » Cod sursa (job #2523921) | Cod sursa (job #2465382) | Cod sursa (job #52294) | Cod sursa (job #2312799) | Cod sursa (job #3217946)
#include <fstream>
#include <stack>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct pt
{
double x, y;
bool operator == (pt const& t) const
{
return x == t.x && y == t.y;
}
};
int i;
int orientation(pt a, pt b, pt c)
{
double v = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
if (v < 0) return -1; // clockwise
if (v > 0) return +1; // counter-clockwise
return 0;
}
bool cw(pt a, pt b, pt c, bool include_collinear)
{
int o = orientation(a, b, c);
return o < 0 || (include_collinear && o == 0);
}
bool collinear(pt a, pt b, pt c)
{
return orientation(a, b, c) == 0;
}
void convex_hull(vector<pt>& a, bool include_collinear = false)
{
pt p0 = *min_element(a.begin(), a.end(), [](pt a, pt b)
{
return make_pair(a.y, a.x) < make_pair(b.y, b.x);
});
sort(a.begin(), a.end(), [&p0](const pt& a, const pt& b)
{
int o = orientation(p0, a, b);
if (o == 0)
return (p0.x-a.x)*(p0.x-a.x) + (p0.y-a.y)*(p0.y-a.y)
< (p0.x-b.x)*(p0.x-b.x) + (p0.y-b.y)*(p0.y-b.y);
return o < 0;
});
if (include_collinear)
{
int i = (int)a.size()-1;
while (i >= 0 && collinear(p0, a[i], a.back())) i--;
reverse(a.begin()+i+1, a.end());
}
vector<pt> st;
for (int i = 0; i < (int)a.size(); i++)
{
while (st.size() > 1 && !cw(st[st.size()-2], st.back(), a[i], include_collinear))
st.pop_back();
st.push_back(a[i]);
}
if (include_collinear == false && st.size() == 2 && st[0] == st[1])
st.pop_back();
a = st;
}
int main()
{
int n;
vector<pt>a;
fin>>n;
for (i=1; i<=n; i++)
{
pt aux;
fin>>aux.x>>aux.y;
a.push_back(aux);
}
convex_hull(a);
fout<<a.size()<<'\n';
reverse(a.begin()+1,a.end());
for (auto it : a)
{
fout<<it.x<<' '<<it.y<<'\n';
}
return 0;
}