Pagini recente » Cod sursa (job #1564358) | Cod sursa (job #2257081) | Cod sursa (job #1272402) | Cod sursa (job #2619154) | Cod sursa (job #475750)
Cod sursa(job #475750)
#include <cstdio>
#include <cmath>
#include <stack>
#include <vector>
#include <algorithm>
#include <iomanip>
#define nmax (120000)
#define PI (3.1415926535897932)
using namespace std;
struct point
{
double x, y, s;
point(double x, double y)
{
this->x = x;
this->y = y;
}
point()
{
x = y = 0;
}
};
vector<point> P;
vector<int> W;
stack<int> S;
int N;
void read()
{
double x, y;
freopen("infasuratoare.in", "r", stdin);
scanf("%d", &N);
for (int i = 0; i < N; ++i)
{
scanf("%lf%lf", &x, &y);
P.push_back(point(x, y));
}
}
inline bool smaller(const double &a, const double &b)
{
return a < b;
}
inline bool compare(const point &P, const point &Q)
{
return smaller(P.s, Q.s);
}
inline bool isleft(const point &P0, const point &P1, const point &P2)
{
return smaller((P2.x - P0.x) * (P1.y - P0.y), (P1.x - P0.x) * (P2.y - P0.y));
}
void solve()
{
point Q(P[0].x, P[0].y);
for (int i = 1; i < N; ++i)
{
if (smaller(P[i].x, Q.x) || !smaller(P[i].x, Q.x) && !smaller(Q.x, P[i].x) && smaller(P[i].y, Q.y))
{
Q = point(P[i].x, P[i].y);
}
}
for (int i = 0; i < N; ++i)
{
P[i].s = atan2(Q.y - P[i].y, Q.x - P[i].x);
P[i].s = (P[i].s < 0? P[i].s + 2 * PI: P[i].s);
}
stable_sort(P.begin(), P.end(), compare);
S.push(0);
S.push(1);
for (int i = 2; i != 1; i = (i + 1) % N)
{
int j, k;
if (S.size() > 1)
{
k = S.top();
S.pop();
j = S.top();
S.push(k);
}
while (S.size() > 1 && !isleft(P[j], P[k], P[i]))
{
S.pop();
if (S.size() > 1)
{
k = S.top();
S.pop();
j = S.top();
S.push(k);
}
}
S.push(i);
}
S.pop();
}
void write()
{
freopen("infasuratoare.out", "w", stdout);
printf("%d\n", S.size());
while (S.size() > 0)
{
W.push_back(S.top());
S.pop();
}
reverse(W.begin(), W.end());
for (vector<int>::iterator i = W.begin(); i != W.end(); ++i)
{
printf("%lf %lf\n", P[*i].x, P[*i].y);
}
}
int main()
{
read();
solve();
write();
return 0;
}