Pagini recente » Cod sursa (job #3122749) | Cod sursa (job #2911169) | Cod sursa (job #3133730) | Cod sursa (job #1452538) | Cod sursa (job #1989860)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct Punct{
double x,y;
};
Punct p[120001];
vector <Punct> st;
int n,nr;
double det(Punct A, Punct B, Punct C){
return (A.x-B.x)*(B.y-C.y)-(A.y-B.y)*(B.x-C.x);
}
bool compd(Punct a,Punct b){
return det(p[1],a,b)<0;
}
bool compx(Punct a,Punct b){
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
}
void citire(){
int minx=1;
f>>n;
for(int i=1;i<=n;i++){
f>>p[i].x>>p[i].y;
if(compx(p[i],p[minx]))
minx=i;
}
swap(p[minx],p[1]);
}
void Graham(){
sort(p+2,p+n+1,compd);
st.reserve(n+1);
st.push_back(p[1]);
st.push_back(p[2]);
for(int i=3;i<=n;i++){
while(st.size()>=2 && det(st[st.size()-2],st[st.size()-1],p[i])>0)
st.pop_back();
st.push_back(p[i]);
}
}
void afisare(){
g<< st.size()<<'\n';
g<<fixed<<setprecision(6);
for(vector<Punct>::reverse_iterator it=st.rbegin();it!=st.rend();++it)
g<< (*it).x<<' '<<(*it).y<<'\n';
}
int main(){
citire();
Graham();
afisare();
return 0;
}