Pagini recente » Cod sursa (job #1637070) | Cod sursa (job #943762) | Cod sursa (job #2661874) | Cod sursa (job #1724037) | Cod sursa (job #3310956)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct ura{
double x,y;
};
bool comp(ura m1, ura m2){
if(m1.x!=m2.x)
return m1.x < m2.x;
return m1.y<m2.y;
}
double miau(ura a1, ura a2, ura a3){
return (a2.x-a1.x)*(a3.y-a1.y)-(a2.y-a1.y)*(a3.x-a1.x);
}
ura a[120001];
vector <int> infasjos;
vector <int> infassus;
vector <int> infas;
int main()
{
int n,i,p;
cin>>n;
for(i=0;i<n;i++)
cin>>a[i].x>>a[i].y;
sort(a,a+n,comp);
for(i=0;i<n;i++){
while(infasjos.size()>=2&&miau(a[infasjos[infasjos.size()-2]],a[infasjos.back()],a[i])<0)
infasjos.pop_back();
infasjos.push_back(i);
}
for(i=n-1;i>=0;i--){
while(infassus.size()>=2&&miau(a[infassus[infassus.size()-2]],a[infassus.back()],a[i])<0)
infassus.pop_back();
infassus.push_back(i);
}
infasjos.pop_back();
infassus.pop_back();
infas=infasjos;
infas.insert(infas.end(),infassus.begin(),infassus.end());
cout<<infas.size()<<endl;
for(i=0;i<infas.size();i++)
cout<<a[infas[i]].x<<" "<<a[infas[i]].y<<endl;
return 0;
}