Pagini recente » Cod sursa (job #66699) | Cod sursa (job #370530) | Cod sursa (job #15012) | Cod sursa (job #2539806) | Cod sursa (job #475745)
Cod sursa(job #475745)
#include <fstream>
#include <cmath>
#include <stack>
#include <vector>
#include <algorithm>
#include <iomanip>
#define nmax (120000)
#define EPS (0.0000000000001)
#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;
stack<int> S;
int N;
void read()
{
double x, y;
ifstream fin("infasuratoare.in");
fin >> N;
for (int i = 0; i < N; ++i)
{
fin >> x >> y;
P.push_back(point(x, y));
}
fin.close();
}
inline bool smaller(const double &a, const double &b)
{
return a < b - EPS;
}
inline bool equal(const double &a, const double &b)
{
return b - EPS < a && a < b + EPS;
}
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 (P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y) > EPS;
}
void solve()
{
point Q(numeric_limits<double>::max(), numeric_limits<double>::max());
for (int i = 0; i < N; ++i)
{
if (smaller(P[i].x, Q.x) || equal(P[i].x, Q.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 < -EPS? P[i].s + 2 * PI: P[i].s);
}
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 reck(ofstream &fout)
{
if (S.size() > 0)
{
int k = S.top();
S.pop();
reck(fout);
fout << setprecision(12) << P[k].x << ' ' << P[k].y << '\n';
}
}
void write()
{
ofstream fout("infasuratoare.out");
fout << S.size() << '\n';
reck(fout);
fout.close();
}
int main()
{
read();
solve();
write();
return 0;
}