Pagini recente » Cod sursa (job #2215543) | Cod sursa (job #1788705) | Cod sursa (job #1012949) | Cod sursa (job #2938248) | Cod sursa (job #2528591)
#include <bits/stdc++.h>
using namespace std;
//ifstream f("date.in");
//ofstream g("date.out");
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int dim = 120005;
int n;
struct str{
double x, y;
}v[dim];
vector <str> st;
inline int semn(str p1, str p2, str p3){
return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}
bool cond(str a, str b){
return semn(v[1], a, b) < 0;
}
bool operator < (str a, str b){
if(a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
void sortare_input(){
int pos = 1;
for (int i = 2; i <= n; ++i)
if (v[i] < v[pos])
pos = i;
swap(v[1], v[pos]);
sort(v + 2, v + n + 1, cond);
}
int main(){
int i;
f >> n;
for(i = 1; i <= n; ++i){
f >> v[i].x >> v[i].y;
}
sortare_input();
st.push_back(v[1]);
st.push_back(v[2]);
for(i = 3; i <= n; ++i){
int last = st.size() - 1;
int intoarcere = 0;
while (intoarcere >= 0 && last > 1){
intoarcere = semn(st[last - 1], st[last], v[i]);
st.pop_back();
--last;
}
st.push_back(v[i]);
}
g << st.size() << '\n';
g << fixed << setprecision(6);
for(int i = st.size() - 1; i >= 0; --i){
str it = st[i];
g << it.x << " " << it.y << '\n';
}
///M-AM SATURAT DEJA CEAPA EI DE PROBLEMA
return 0;
}