Pagini recente » Cod sursa (job #2667005) | Cod sursa (job #2895607) | Cod sursa (job #1538965) | Cod sursa (job #1235217) | Cod sursa (job #2521196)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
int n, i, j, k, pminim;
struct punct {
double first, second;
};
punct v[120001], s[120001];
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
double arie (punct a, punct b, punct c) {
return (b.first-a.first)*(c.second-a.second) - (c.first-a.first)*(b.second-a.second);
}
int cmp (punct a, punct b)
{
punct c;
c.first=0;
c.second=0;
int d=arie(c, a, b);
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;
pminim=0;
v[0].first=1.0*1000000001;
v[0].second=1.0*1000000001;
for (i=1;i<=n;i++) {
fin>>v[i].first>>v[i].second;
if (v[i].second<v[pminim].second || ( (v[i].second==v[pminim].second) && (v[i].first<v[pminim].first) ))
pminim=i;
}
v[0]=v[pminim];
v[pminim]=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 (arie(v[1], v[2], v[j]))
break;
}
i=2;
j--;
while (i<j) {
swap(v[i], v[j]);
i++;
j--;
}
s[1]=v[1];
s[2]=v[2];
k=2;
for (j=3;j<=n;j++) {
while (k>=2 && arie(s[k-1], s[k], v[j])<0) {
k--;
}
s[++k]=v[j];
}
fout<<k<<"\n";
for (i=1;i<=k;i++) {
fout<<fixed<<setprecision(6)<<s[i].first+v[0].first<<" "<<s[i].second+v[0].second<<"\n";
}
return 0;
}