Pagini recente » Cod sursa (job #2759918) | Cod sursa (job #991630) | Statistici Nicolae (nicu122) | Cod sursa (job #478614) | Cod sursa (job #2224828)
#include<fstream>
#include<vector>
#include<utility>
#include<algorithm>
#include<iomanip>
using namespace std;
vector< pair<double, double> > a, st;
int n, inf=2000000000;
double xr, yr;
double det(pair<double, double> p1, pair<double, double> p2, pair<double, double> p3) {
return p1.first*p2.second + p2.first*p3.second + p1.second*p3.first - p3.first*p2.second - p3.second*p1.first - p2.first*p1.second;
}
double polar(pair<double, double> p) {
double xc = p.first;
double yc = p.second;
if (xc==xr && yc<yr) return -inf;
else if (xc==xr && yc>yr) return inf;
else if (xc==xr && yc==yr) return -inf-1;
else return (yc-yr)/(xc-xr);
}
bool cmp(pair<double, double> p1, pair<double, double> p2) {
return polar(p1)<polar(p2);
}
int main(void) {
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin>>n; xr=2000000000;
for (int i=1; i<=n; ++i){
double x, y; cin>>x>>y;
if (x<xr) { xr=x; yr=y; }
else if (x==xr && y<yr) yr=y;
a.push_back(make_pair(x,y));
}
sort(a.begin(), a.end(), cmp);
st.push_back(a[0]);
st.push_back(a[1]);
for (int i=2; i<a.size(); ++i) {
while (st.size()>1 && det(st[st.size()-2], st[st.size()-1], a[i])<0) { auto it=st.end(); --it; st.erase(it); }
st.push_back(a[i]);
}
cout<<st.size()<<"\n";
for (int i=0; i<st.size(); ++i) cout<<setprecision(10)<<fixed<<st[i].first<<" "<<st[i].second<<"\n";
return 0;
}