Pagini recente » Cod sursa (job #1026612) | Cod sursa (job #179281) | Cod sursa (job #2557655) | Cod sursa (job #2850791) | Cod sursa (job #1142671)
#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[])
{
double x, y;
int n;
FILE* fin = fopen("infasuratoare.in", "r");
FILE* fout = fopen("infasuratoare.out", "w");
fscanf(fin, "%d", &n);
vector<pair<double, double> > polygon;
double smallest_x, smallest_y;
bool first = true;
for (int i = 0; i < n; i++) {
fscanf(fin, "%lf %lf", &x, &y);
if (first || x < smallest_x || (x == smallest_x && y < smallest_y)) {
if (!first)
polygon.push_back(make_pair(smallest_x, smallest_y));
smallest_y = y;
smallest_x = x;
first = false;
} else {
polygon.push_back(make_pair(x, y));
}
}
referencePoint = make_pair(smallest_x, smallest_y);
sort(polygon.begin(), polygon.end(), compare);
polygon.push_back(referencePoint);
// cout << "ref " << referencePoint << endl;
// for (int i = 0; i < n; i++) {
// cout << polygon[i] << " ";
// }
// cout << endl;
vector<pair<double, double> > deq;
deq.push_back(referencePoint);
deq.push_back(polygon[0]);
int pos = 1;
while (pos < n) {
// cout << endl << endl;
pair<double, double> next_point = polygon[pos++];
pair<double, double> pp1 = deq[deq.size() - 1];
pair<double, double> pp2 = deq[deq.size() - 2];
// cout << "deq: " << deq.size() << endl;
// cout << "next_point: " << next_point << endl;
// cout << "pos: " << pos << endl;
// for (int i = 0; i < deq.size(); i++) {
// cout << deq[i] << " ";
// }
// cout << endl;
while (!going_left(pp1, pp2, next_point)) {
// cout << "Removing point " << pp1 << endl;
deq.pop_back();
pp1 = deq[deq.size() - 1];
pp2 = deq[deq.size() - 2];
}
deq.push_back(next_point);
}
fprintf(fout, "%d\n", deq.size() - 1);
for (int i = 0; i < deq.size() - 1; i++) {
fprintf(fout, "%.6lf %.6lf\n",
deq[i].first,
deq[i].second);
}
return 0;
}