Pagini recente » Cod sursa (job #1876896) | Cod sursa (job #1846329) | Cod sursa (job #1099971) | Cod sursa (job #1251322) | Cod sursa (job #3195728)
#include <bits/stdc++.h>
std::ifstream f("infasuratoare.in");
std::ofstream g("infasuratoare.out");
struct coord{
double y, x;
};
int n;
std::vector<coord> v,s;
double orientation(const coord& a, const coord& b, const coord& c){
return (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
}
bool trigComp(const coord& a, const coord& b){
return orientation(v[0],a,b)<0;
}
int main(){
f>>n;
double mx=DBL_MAX;
int mi=0;
for(int i=0;i<n;i++){
double a, b;
f>>a>>b;
if(a<mx){
mx=a;
mi=i;
}
v.push_back({a,b});
}
std::swap(v[0],v[mi]);
std::sort(v.begin()+1,v.end(),trigComp);
s.push_back(v[0]);
s.push_back(v[1]);
for(int i=2;i<n;i++){
int h=s.size()-1;
while(h>=1 && orientation(s[h-1],s[h],v[i])>0){
h--;
s.pop_back();
}
s.push_back(v[i]);
}
g<<s.size()<<'\n';
g<<std::setprecision(12)<<std::fixed;
while(!s.empty()){
g<<s.back().y<<' '<<s.back().x<<'\n';
s.pop_back();
}
return 0;
}