Pagini recente » Cod sursa (job #109359) | Cod sursa (job #2206915) | Cod sursa (job #3265662) | Cod sursa (job #24587) | Cod sursa (job #2539215)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
pair <double, double> v[120005], top1, top2;
stack <pair<double, double> > stiva;
int n, pmin, i, j;
double det (double x1, double y1, double x2, double y2, double x3, double y3) {
return (x2 - x1)*(y3 - y1) - (x3 - x1)*(y2 - y1);
}
double cmp (const pair<double, double> &a, const pair<double, double> &b) {
double d = det (v[1].first, v[1].second, a.first, a.second, b.first, b.second);
if (d != 0)
return d > 0;
else
return a.first*a.first + a.second*a.second > b.first*b.first + b.second*b.second;
}
int main(){
fin >> n;
v[0] = {INT_MAX, INT_MAX};
for (i=1; i<=n; i++){
fin >> v[i].first >> v[i].second;
if (v[i].second < v[pmin].second || (v[i].second == v[pmin].second && v[i].first < v[pmin].first)){
pmin = i;
}
}
v[0] = v[pmin], v[pmin] = v[1], v[1] = v[0];
sort (v + 2, v + n + 1, cmp);
for (j=3; j<=n; j++){
if (det (v[1].first, v[1].second, v[2].first, v[2].second, v[j].first, v[j].second) != 0.0){
break;
}
}
i = 2, j--;
while (i < j){
swap (v[i], v[j]);
i++, j--;
}
stiva.push (v[2]);
top2 = v[2];
stiva.push (v[1]);
top1 = v[1];
for (i=3; i<=n; i++){
while (stiva.size() >= 2 && det (top2.first, top2.second, top1.first, top1.second, v[i].first, v[i].second) <= 0.0){
top1 = stiva.top();
stiva.pop();
top2 = stiva.top();
}
stiva.push (v[i]);
}
fout << stiva.size() << "\n";
while (!stiva.empty()){
fout << fixed<<setprecision(6) << (int)1000000*stiva.top().first/1000000.0 << " " << (int)1000000*stiva.top().second/1000000.0 << "\n";
stiva.pop();
}
return 0;
}