Pagini recente » Cod sursa (job #2597153) | Cod sursa (job #2195583) | Cod sursa (job #2919972) | Cod sursa (job #1617863) | Cod sursa (job #944029)
Cod sursa(job #944029)
#include <fstream>
#include <cstdio>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<double, double> pdd;
typedef vector<pdd> vdd;
pdd leftDown;
pdd operator-(const pdd& a, const pdd& b) {
return pdd(a.first - b.first, a.second - b.second);
}
double operator*(const pdd& a, const pdd& b) {
return (a.first * b.second - a.second * b.first);
}
bool cmp(const pdd& a, const pdd& b) {
return ((a - leftDown) * (b - leftDown)) > 0;
}
void solve(vdd& v, vdd& ans) {
int pos = 0, l = v.size();
for(int i = 1; i < l; i++)
if(v[i] < v[pos]) pos = i;
swap(v[pos], v[0]);
leftDown = v[pos];
sort(v.begin() + 1, v.end(), cmp);
ans.push_back(v[0]);
ans.push_back(v[1]);
for(int i = 2; i < l; i++) {
while(
ans.size() > 2 &&
(ans.back() - ans[ans.size() - 2]) * (v[i] - ans.back()) < 0.0
) ans.pop_back();
ans.push_back(v[i]);
}
}
int main(){
int n, h;
ifstream f("infasuratoare.in");
f >> n;
vdd v(n), ans;
for(int i = 0; i < n; i++)
f >> v[i].first >> v[i].second;
f.close();
solve(v, ans);
FILE* g = fopen("infasuratoare.out", "wt");
h = ans.size();
fprintf(g, "%d\n", h);
for(int i = 0; i < h; i++)
fprintf(g, "%.6lf %.6lf\n", ans[i].first, ans[i].second);
fclose(g);
return 0;
}