Pagini recente » Cod sursa (job #2036905) | Cod sursa (job #2526202)
#include <bits/stdc++.h>
using namespace std;
//#define f cin
//#define g cout
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int dim = 101;
int n;
struct str{
int x, y;
double tg;
}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){
/*if(a.tg != b.tg)
return a.tg < b.tg;
if(a.x != b.x)
return a.x < b.x;
return a.y < b.y;*/
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 + 1, v + n + 1, cond);
}
int main(){
int i;
f >> n;
for(i = 1; i <= n; ++i){
f >> v[i].x >> v[i].y;
if(v[i].y == 0)
v[i].tg = 1111111111;
else v[i].tg = (double)v[i].x / v[i].y;
}
sortare_input();
for(i = 1; i <= n; ++i){
g << v[i].x << " " << v[i].y << '\n';
}
st.push_back(v[1]);
st.push_back(v[2]);
for(i = 3; i <= n; ++i){
int last = st.size() - 1;
int intoarcere = semn(st[last - 1], st[last], v[i]);
if(intoarcere == 0){
st.pop_back();
st.push_back(v[i]);
} else if(intoarcere < 0){
st.push_back(v[i]);
} else {
while (intoarcere > 0 && last > 1){
st.pop_back();
--last;
intoarcere = semn(st[last - 1], st[last], v[i]);
}
st.push_back(v[i]);
}
}
g << st.size() << '\n';
for(auto it: st)
g << it.x << " " << it.y << '\n';
return 0;
}