Pagini recente » Cod sursa (job #2028297) | Cod sursa (job #237129) | Cod sursa (job #683163) | Cod sursa (job #633446) | Cod sursa (job #2169793)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define pdd pair<long double,long double>
#define Nmax 120003
#define ld long double
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,sav;
pdd bst;
pdd P[Nmax];
vector<pdd> H;
ld area(pdd a,pdd b,pdd c){
return a.first*b.second + a.second * c.first + b.first * c.second - a.first * c.second - a.second * b.first - b.second * c.first;
}
bool comp(pdd a,pdd b){
return area(bst,a,b)>0;
}
int main()
{
f>>n;
bst = {1e9,1e9};
for (int i=1;i<=n;i++){
f>>P[i].first>>P[i].second;
if ((P[i].first<bst.first) || (P[i].first == bst.first && P[i].second<bst.second)){
sav = i;
bst = P[i];
}
}
for (int i=sav;i<n;i++) P[i] = P[i+1];
n--;
sort(P+1,P+n+1,comp);
H.push_back(bst);
for (int i=1;i<=n;i++){
while (H.size()>=2 && area(H[H.size()-2],H.back(),P[i])<=0) H.pop_back();
H.push_back(P[i]);
}
g<<H.size()<<'\n';
for (auto it : H) g<<fixed<<setprecision(12)<<it.first<<' '<<it.second<<'\n';
return 0;
}