Pagini recente » Cod sursa (job #27371) | Cod sursa (job #2101339) | Cod sursa (job #1487149) | Cod sursa (job #2301348) | Cod sursa (job #445995)
Cod sursa(job #445995)
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <stack>
#define FIN "infasuratoare.in"
#define FOUT "infasuratoare.out"
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define FORI(i, v, T) for(T::iterator i = v.begin(); i != v.end(); ++i)
#define INF 1000000000
using namespace std;
typedef pair<double, double> POINT;
vector<POINT > pts;
stack<POINT* > st;
class Sorter
{
POINT *orig;
public:
Sorter(POINT *p)
{
orig = p;
}
static bool left(POINT& p1, POINT& p2, POINT& p3)
{
return (long double)(p3.first - p1.first) * (long double)(p2.second - p1.second) <
(long double)(p2.first - p1.first) * (long double)(p3.second - p1.second);
}
bool operator() (const POINT& p1, const POINT& p2) const
{
return (long double)(p1.first - orig->first) * (long double)(p2.second - orig->second) >
(long double)(p2.first - orig->first) * (long double)(p1.second - orig->second);
}
};
void printStack(stack<POINT* >& st)
{
if (!st.empty())
{
POINT *p = st.top();
st.pop();
printStack(st);
printf("%lf %lf\n", p->first, p->second);
}
}
int main()
{
int n, orig;
POINT origPt(INF, INF);
FILE *fin = freopen(FIN, "r", stdin), *fout = freopen(FOUT, "w", stdout);
scanf("%d", &n);
FOR(i, n)
{
double x, y;
scanf("%lf %lf", &x, &y);
pts.push_back(make_pair(x, y));
if (x < origPt.first || x == origPt.first && y < origPt.second)
origPt.first = x, origPt.second = y, orig = i;
}
swap(pts[orig], pts[pts.size() - 1]);
pts.pop_back();
sort(pts.begin(), pts.end(), Sorter(&origPt));
st.push(&origPt);
st.push(&pts[0]);
st.push(&pts[1]);
FORI(it, pts, vector<POINT >)
if (it > pts.begin() + 1)
{
POINT *p;
p = st.top();
st.pop();
while (!Sorter::left(*st.top(), *p, *it))
{
p = st.top();
st.pop();
}
st.push(p);
st.push(&(*it));
}
printf("%d\n", st.size());
printStack(st);
fclose(fout);
return 0;
}