Pagini recente » Cod sursa (job #1745221) | Cod sursa (job #1423025) | Cod sursa (job #1745228) | Cod sursa (job #843609) | Cod sursa (job #2539701)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
pair <double,double>p[500005],v[500005];
int top,n,ll,m;
double minix=1000000009,miniy=1000000009;
int semn(double ax,double ay,double bx,double by,double cx,double cy){
double arie;
arie=(ax-bx)*(ay-cy)-(ay-by)*(ax-cx);
if(arie<0){
return -1;
}
else
return 1;
}
bool cmp(pair<double,double>a,pair<double,double>b){
return (a.second*b.first<b.second*a.first);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>p[i].first>>p[i].second;
if(p[i].second<miniy){
minix=p[i].first;
miniy=p[i].second;
}
else{
if(p[i].second==miniy){
if(p[i].first<minix){
minix=p[i].first;
}
}
}
}
for(int i=1;i<=n;i++){
p[i].first-=minix;
p[i].second-=miniy;
if(p[i].first!=0 || p[i].second !=0)
p[++m]=p[i];
}
n=m;
/*v[1].first=minix;
v[1].second=miniy;
v[n+1].first=minix;
v[n+1].second=miniy;
*/
sort(p+1,p+n+1,cmp);
p[n+1]=p[1];
v[1].first=0;
v[1].second=0;
v[2].first=p[1].first;
v[2].second=p[1].second;
v[3].first=p[2].first;
v[3].second=p[2].second;
top=3;
for(int i=3;i<=n+1;i++){
while(semn(v[top-2].first,v[top-2].second,v[top-1].first,v[top-1].second,v[top].first,v[top].second)!=semn(v[top-1].first,v[top-1].second,v[top].first,v[top].second,p[i].first,p[i].second)){
v[top].first=0;
v[top].second=0;
top--;
}
top++;
v[top].first=p[i].first;
v[top].second=p[i].second;
}
top--;
cout<<top<<'\n';
for(int i=1;i<=top;i++,cout<<'\n'){
cout<<setprecision(6)<<v[i].first+minix<<" "<<setprecision(6)<<v[i].second+miniy;
}
return 0;
}