Pagini recente » Cod sursa (job #743971) | Cod sursa (job #3320239) | Monitorul de evaluare | Borderou de evaluare (job #3311881) | Cod sursa (job #3345595)
#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){
mx = x;
prim = i;
}
}
slope.resize(n);
slope[0].c = prim;
j = 1;
for(int i = 0; i < n; i++){
if(i != prim){
if(v[i].l - mx == 0){
slope[j].l = 1e200;
}else{
slope[j].l = (v[i].c - my) / (v[i].l - mx);
}
slope[j].c = i;
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;
for(int i = 2; i < n; i++){
p1 = st[st.size() - 2];
p2 = st[st.size() - 1];
p3 = slope[i].c;
while(trigo(v[p1], v[p2], v[p3]) == true){
st.pop_back();
if(st.size() < 2){
break;
}
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;
}