Pagini recente » Cod sursa (job #1589505) | Cod sursa (job #2647311) | Cod sursa (job #1499774) | Cod sursa (job #609379) | Cod sursa (job #1977497)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define err 1e-12
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int NMAX = 120000;
struct data{
double x;
double y;
};
int n, h, last, q, st[1 + NMAX], ok[1 + NMAX];
data v[1 + NMAX];
int check(double a, double b){
if(a + err < b)
return 1;
else if(b + err < a)
return -1;
return 0;
}
bool cmp(data a, data b){
int answer = check(a.x, b.x);
if(answer != 0){
return (answer == 1);
}else{
return(check(a.y, b.y) == 1);
}
}
int sgn(data a, data b, data c){
double x1, y1, z1;
x1 = a.y - b.y;
y1 = b.x - a.x;
z1 = a.x * b.y - b.x * a.y;
return check(x1 * c.x + y1 * c.y + z1, 0);
}
void solve(){
int node;
sort(v + 1, v + n + 1, cmp);
st[1] = 1;
st[2] = 2;
ok[2] = 1;
node = 3;
last = 2;
q = 1;
while(ok[1] == 0){
while(ok[node]){
if(node == n)
q = -1;
node += q;
}
while(last >= 2 && sgn(v[st[last - 1]], v[st[last]], v[node]) == -1){
ok[st[last]] = 0;
last--;
}
st[++last] = node;
ok[node] = 1;
}
h = last - 1;
}
void write(){
out << h << '\n';
out << setprecision(6) << fixed;
for(int i = h; i >= 2; i--){
out << v[st[i]].x << ' ' << v[st[i]].y << '\n';
}
out << v[st[h + 1]].x << ' ' << v[st[h + 1]].y << '\n';
//for(int i = 2; i <= h + 1; i++){
// out << st[i] << ' ';// << ' ' << v[st[i]].y << '\n';
//}
}
int main()
{
in >> n;
for(int i = 1; i <= n; i++){
in >> v[i].x >> v[i].y;
}
in.close();
solve();
write();
out.close();
return 0;
}