Pagini recente » Atasamentele paginii Profil DumitruRG | Borderou de evaluare (job #3347062) | Borderou de evaluare (job #3306356) | Borderou de evaluare (job #2703988) | Cod sursa (job #3345593)
#include <bits/stdc++.h>
using namespace std;
struct jd{
double l, c;
};
jd v[120005];
vector<jd> slope;
bool cmp(jd a, jd b){
if(a.l <= 0 && b.l >= 0){
return a.l < b.l;
}else if(b.l <= 0 && a.l >= 0){
return a.l < b.l;
}
return a.l > b.l;
}
bool trigo(jd x, jd y, jd z){
double res;
res = x.l * y.c - x.c * y.l + y.l * z.c - y.c * z.l + z.l * x.c - z.c * x.l;
return res > 0;
}
vector<double> st;
int main()
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
double n, x, y, mx = 1000000001, my = 1000000001, prim;
int j;
cin >> n;
for(int i = 0; i < n; i++){
cin >> x >> y;
v[i].l = x;
v[i].c = y;
if(my > y){
mx = x;
prim = i;
my = y;
}else if(my == y && mx > x){
my = y;
prim = i;
}
}
slope.resize(n);
j = 1;
for(int i = 0; i < n; i++){
if(i != prim){
if(v[j].l - mx == 0){
slope[j].l = 0;
}else{
slope[j].l = (v[j].c - my) / (v[j].l - mx);
}
slope[j].c = j;
j++;
}
}
sort(slope.begin() + 1, slope.end(), cmp);
st.push_back(slope[0].c);
st.push_back(slope[1].c);
/*for(int i = 0; i < n - 1; i++){
cout << slope[i].l << " " << slope[i].c << "\n";
}*/
int p1, p2, p3, k;
for(int i = 2; i < n; i++){
p1 = st[st.size() - 2];
p2 = st[st.size() - 1];
k = st.size() - 1;
p3 = slope[i].c;
while(trigo(v[p1], v[p2], v[p3]) == true){
st.resize(k);
k--;
p1 = st[st.size() - 2];
p2 = st[st.size() - 1];
}
st.push_back(p3);
}
cout << st.size() << "\n";
cout << fixed << setprecision(12) << v[(int)st[0]].l << " ";
cout << fixed << setprecision(12) << v[(int)st[0]].c << "\n";
for(int i = st.size() - 1; i > 0; i--){
cout << fixed << setprecision(12) << v[(int)st[i]].l << " ";
cout << fixed << setprecision(12) << v[(int)st[i]].c << "\n";
}
return 0;
}