Pagini recente » Cod sursa (job #509449) | Cod sursa (job #2534604) | Cod sursa (job #440396) | Cod sursa (job #2558580) | Cod sursa (job #1142646)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <deque>
#include <iomanip>
using namespace std;
pair<double, double> referencePoint;
bool compare (pair<double, double> a, pair<double, double> b) {
/** In general, it's good to avoid division, to keep away from arithmetic errors.
In this case, using the code below will lead to wrong results.
*/
// double anglea = (a.second - referencePoint.second) / (a.first - referencePoint.first);
// double angleb = (b.second - referencePoint.second) / (b.first - referencePoint.first);
// return anglea < angleb;
return
(a.second - referencePoint.second) * (b.first - referencePoint.first) <
(b.second - referencePoint.second) * (a.first - referencePoint.first);
}
bool going_left(pair<double, double> p1,
pair<double, double> p2,
pair<double, double> p3) {
double res =
(p2.first - p1.first) * (p3.second - p1.second) -
(p2.second - p1.second) * (p3.first - p1.first);
return
(p2.first - p1.first) * (p3.second - p1.second) -
(p2.second - p1.second) * (p3.first - p1.first) < 0;
}
ostream& operator << (ostream& os, const pair<double, double> &a) {
os << "(" << a.first << ", " << a.second << ")";
return os;
}
int main(int argc, char *argv[])
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
double x, y;
int n;
f >> n;
vector<pair<double, double> > polygon;
double smallest_x = 123456789.0;
double smallest_y = 123456789.0;
for (int i = 0; i < n; i++) {
f >> x >> y;
polygon.push_back(make_pair(x, y));
if (y < smallest_y || (y == smallest_y && x < smallest_x)) {
smallest_y = y;
smallest_x = x;
}
}
referencePoint = make_pair(smallest_x, smallest_y);
sort(polygon.begin(), polygon.end(), compare);
vector<pair<double, double> > deq;
deq.push_back(polygon[0]);
deq.push_back(polygon[1]);
int pos = 2;
while (pos < n) {
pair<double, double> next_point = polygon[pos++];
pair<double, double> pp1 = deq[deq.size() - 1];
pair<double, double> pp2 = deq[deq.size() - 2];
while (!going_left(pp1, pp2, next_point)) {
deq.pop_back();
pp1 = deq[deq.size() - 1];
pp2 = deq[deq.size() - 2];
}
deq.push_back(next_point);
}
g << fixed << setprecision(6);
g << deq.size() << endl;
for (int i = 0; i < deq.size(); i++) {
g << deq[i].first << " " << deq[i].second << endl;
}
return 0;
}