Pagini recente » Cod sursa (job #966855) | Cod sursa (job #591922) | Cod sursa (job #229557) | Cod sursa (job #1677169) | Cod sursa (job #724381)
Cod sursa(job #724381)
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <string>
#include <cstdio>
#include <algorithm>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct point {
double x;
double y;
};
vector <point> p;
vector <point> q;
void read() {
int n;
in >> n;
while (n--) {
point P;
in >> P.x >> P.y;
p.push_back(P);
}
}
inline bool comp(point P, point Q) {
if (P.x == Q.x)
return (P.y < Q.y);
return (P.x < Q.x);
}
inline bool turnsRight(point a, point b, point c) {
double baz = a.x * b.y + c.x * a.y + b.x * c.y;
baz -= a.x * c.y + c.x * b.y + b.x * a.y;
return (baz > 0);
}
void addToStack(point x) {
while (q.size() > 1 && turnsRight(q[q.size() - 2], q[q.size() - 1], x))
q.pop_back();
q.push_back(x);
}
void solve() {
q.push_back(p[0]);
for (int i = 1; i < (int)p.size(); ++i)
addToStack(p[i]);
for (int i = p.size() - 2; i >= 0; --i)
addToStack(p[i]);
q.pop_back();
}
void print()
{
out << q.size() << "\n";
freopen("infasuratoare.out", "w", stdout);
for (int i = q.size() - 1; i >= 0; --i)
printf("%12f %12f\n", q[i].x, q[i].y);
}
int main() {
read();
sort(p.begin(), p.end(), comp);
solve();
print();
return 0;
}