Pagini recente » Cod sursa (job #349771) | Cod sursa (job #2293686) | Cod sursa (job #767909) | Cod sursa (job #49781) | Cod sursa (job #3000760)
#include<bits/stdc++.h>
#define DIM 1000001
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair <double, double> v[DIM], st[DIM], aux;
int pmin, i, j, n, k;
double det(double X1, double Y1, double X2, double Y2, double X3, double Y3){
return (X2 - X1) * (Y3 - Y1) - (X3 - X1) * (Y2 - Y1);
}
bool cmp(const pair <double, double> &a, const pair <double, double> &b){
double d = det(0, 0, 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[pmin].first = DIM;
v[pmin].second = DIM;
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];
for(i=1;i<=n;i++){
v[i].first -= v[0].first;
v[i].second -= v[0].second;
}
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))
break;
i = 2;
j--;
while(i < j){
aux = v[i];
v[i] = v[j];
v[j] = aux;
i++;
j--;
}
st[1] = v[1];
st[2] = v[2];
k = 2;
for(i=3;i<=n;i++){
while(k >= 2 && det(st[k - 1].first, st[k - 1].second, st[k].first, st[k].second, v[i].first, v[i].second) < 0)
k--;
st[++k] = v[i];
}
fout << k << "\n";
for(i=1;i<=k;i++)
fout << fixed << setprecision(12) << st[i].first + v[0].first << " " << fixed << setprecision(12) << st[i].second + v[0].second << "\n";
}