Pagini recente » Cod sursa (job #554977) | Cod sursa (job #2270736) | Cod sursa (job #2598536) | Cod sursa (job #1540494) | Cod sursa (job #1114904)
#include<iostream>
#include<cmath>
#include<algorithm>
#include<fstream>
#include<iomanip>
#define PI 3.14159265
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct{
double x; double y;
};
punct p0, p1, p2, p3, p4, p[120000], s[120000];
int n;
int varf;
void push(punct p){
++varf; s[varf] = p;
}
int prod(punct p1, punct p2, punct p3){
return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}
void afis(){
int i; fout << fixed;
fout << varf << '\n';
for (i = varf; i >= 1; i--)
fout << setprecision(9) << s[i].x << " " << s[i].y << '\n';
}
void afisn(){
int i;
fout << n << '\n';
for (i = 1; i <= n; i++)
fout << p[i].x << " " << p[i].y << '\n';
}
int cmp(punct p1, punct p2) {
return prod(p[1], p1, p2) < 0;
}
void infas(){
int i; double o; int poz = 1;
for (int i = 2; i <= n; ++i){
if (p[i].y < p[poz].y)
poz = i;
else if (p[i].y == p[poz].y and p[i].x < p[poz].x)
poz = i;
}
swap(p[1], p[poz]);
sort(p + 2, p + n + 1, cmp);
// afisn();
varf = 2; s[1] = p[1]; s[2] = p[2];
for (int i = 3; i <= n; i++) {
o = prod(s[varf - 1], s[varf], p[i]);
if (o == 0){
varf--;
push(p[i]); }
else
if (o > 0) push(p[i]);
else {
while (o <= 0 and varf >= 2){
varf--;
o = prod(s[varf - 1], s[varf], p[i]);
}
push(p[i]);
}
}
afis();
}
int main() {
fin >> n; int i;
for (i = 1; i <= n; i++)
fin >> p[i].x >> p[i].y;
infas();
}