Pagini recente » Rating Irina Tenita (tenirina) | Cod sursa (job #3177199) | Cod sursa (job #3174935) | Cod sursa (job #3286110) | Cod sursa (job #492459)
Cod sursa(job #492459)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const char iname[] = "infasuratoare.in";
const char oname[] = "infasuratoare.out";
int turnsRight(pair <double, double> a, pair <double, double> b, pair <double, double> c) {
/* b.first -= a.first, b.second -= a.second;
c.first -= a.first, c.second -= a.second;
return (b.first * c.second - b.second * c.first) < 0;
*/
double c1 = a.second - b.second;
double c2 = b.first - a.first;
double c3 = a.first * b.second - a.second * b.first;
double ecuation = c1 * c.first + c2 * c.second + c3;
return (ecuation < 0);
}
int main(void) {
int n; double x, y;
vector < pair <double, double> > points;
ifstream in(iname);
in >> n;
for (int i = 0; i < n; ++ i)
in >> x >> y, points.push_back(make_pair(x, y));
in.close();
sort(points.begin(), points.end());
vector < pair <double, double> > stk;
stk.push_back(points[0]), stk.push_back(points[1]);
for (int i = 2; i < (int) points.size(); ++ i) {
while (stk.size() > 1 && turnsRight(stk[stk.size() - 2], stk[stk.size() - 1], points[i]))
stk.pop_back();
stk.push_back(points[i]);
}
for (int i = (int) points.size() - 2; i >= 0; -- i) {
while (stk.size() > 1 && turnsRight(stk[stk.size() - 2], stk[stk.size() - 1], points[i]))
stk.pop_back();
stk.push_back(points[i]);
}
stk.pop_back();
ofstream out(oname);
out << stk.size() << '\n';
for (int i = 0; i < (int) stk.size(); ++ i)
out << stk[i].first << ' ' << stk[i].second << '\n';
out.close();
return 0;
}