Pagini recente » Cod sursa (job #805072) | Cod sursa (job #651571) | Cod sursa (job #356458) | Cod sursa (job #1795219) | Cod sursa (job #2539210)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
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;
}
pair <double, double> v[120005], stiva[120005];
int n, pmin, i, j, k;
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[1] = v[1], stiva[2] = v[2], k = 2;
for (i=3; i<=n; i++){
while (k >= 2 && det (stiva[k-1].first, stiva[k-1].second, stiva[k].first, stiva[k].second, v[i].first, v[i].second) <= 0.0){
k--;
}
stiva[++k] = v[i];
}
fout << k << "\n";
for (i=1; i<=k; i++){
fout << fixed << setprecision(6) << (int)1000000*stiva[i].first/1000000.0 << " " << (int)1000000*stiva[i].second/1000000.0 << "\n";
}
return 0;
}