Pagini recente » Cod sursa (job #489157) | Cod sursa (job #798916) | Cod sursa (job #1046133) | Cod sursa (job #2085512) | Cod sursa (job #1370360)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, nq;
const double EPS = 1;
struct punct
{
double x, y;
punct(double x=0, double y=0) : x(x), y(y)
{
}
bool operator()(punct a, punct b)
{
return (a.x == b.x ? a.y < b.y : a.x < b.x);
}
}a[120012];
void citire()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%lf %lf", &a[i].x, &a[i].y);
// cin >> a[i].x;
// cin >> a[i].y;
}
}
double determinant(punct f, punct g, punct h)
{
return f.x *(g.y-h.y) + h.x * (f.y-g.y) + g.x *(h.y-f.y);
}
inline double det(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);
}
double cross_product(punct O, punct A, punct B) {
return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}
void operate(vector<punct> &st, punct g)
{
while(st.size() >= 2 && det(st[st.size()-2], st[st.size()-1], g) < 0)//determinant(st[st.size()-1], st[st.size()-2], g) > 0.0001)
{
st.pop_back();
// cerr << determinant(st[st.size()-1], st[st.size()-2], g) - cross_product(st[st.size()-1], st[st.size()-2], g);
//cerr << "\n";
}
st.push_back(g);
}
void solve()
{
sort(a, a+n, punct());
vector<punct> st;
st.push_back(a[0]); st.push_back(a[1]);
for (int i = 2; i < n; i++)
operate(st, a[i]);
for (int i = n-2; i >= 0; i--)
operate(st, a[i]);
st.pop_back();
printf("%d\n", st.size());
for (int i = 0; i < st.size(); i++)
printf("%lf %lf\n", st[i]);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
citire();
solve();
return 0;
}