Pagini recente » Cod sursa (job #3293837) | Cod sursa (job #2923120) | Statistici Delia Draghici (delia_99) | Cod sursa (job #17922) | Cod sursa (job #492461)
Cod sursa(job #492461)
#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;
}
int main(void) {
int n; double x, y;
vector < pair <double, double> > points;
FILE *fi = fopen(iname, "r");
fscanf(fi, "%d", &n);
for (int i = 0; i < n; ++ i)
fscanf(fi, "%lf %lf", &x, &y), points.push_back(make_pair(x, y));
fclose(fi);
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();
FILE *fo = fopen(oname, "w");
fprintf(fo, "%d\n", stk.size());
for (int i = 0; i < (int) stk.size(); ++ i)
fprintf(fo, "%lf %lf\n", stk[i].first, stk[i].second);
fclose(fo);
return 0;
}