Pagini recente » Cod sursa (job #1640330) | Cod sursa (job #45843) | Cod sursa (job #423814) | Cod sursa (job #3191874) | Cod sursa (job #2937614)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
struct punct{
double x,y;
}v[120001],stjs,drss;
vector<punct>S1;
vector<punct>S2;
void Citire(){
fin>>n;
for(int i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
}
int cmp(punct a,punct b){
if(a.x<b.x || (a.x==b.x && a.y<b.y))
return 1;
return 0;
}
int getOrientation(punct P1, punct P2, punct P3){
int det = (P2.x-P1.x)*(P3.y-P1.y)-(P3.x-P1.x)*(P2.y-P1.y);
if (det > 0)
return 0;
if (det < 0)
return 1;
return 2;
}
int Finder(){
int rez=0,minim=10000;
for(int i=0;i<S1.size();i++)
if(S1[i].y<minim)
minim=S1[i].y,rez=i;
return rez;
}
int main()
{
Citire();
sort(v+1,v+n+1,cmp);
S1.push_back(v[1]);
S1.push_back(v[2]);
for(int i=3;i<=n;i++){
while(S1.size() > 1 && getOrientation(S1[S1.size()-2],S1[S1.size()-1],v[i])==1){
S1.pop_back();
}
S1.push_back(v[i]);
}
S2.push_back(v[n]);
S2.push_back(v[n-1]);
for(int i=n-3;i>=1;i--){
while(S2.size() > 1 && getOrientation(S2[S2.size()-2],S2[S2.size()-1],v[i])==1){
S2.pop_back();
}
S2.push_back(v[i]);
}
fout<<S1.size()+S2.size()-2<<"\n";
int start=Finder();
for(int i=start;i<S1.size();i++)
fout<<fixed<<setprecision(14)<<S1[i].x<<" "<<S1[i].y<<"\n";
for(int i=1;i<S2.size()-1;i++)
fout<<fixed<<setprecision(14)<<S2[i].x<<" "<<S2[i].y<<"\n";
for(int i=start-1;i>=0;i--)
fout<<fixed<<setprecision(14)<<S1[i].x<<" "<<S1[i].y<<"\n";
return 0;
}