Pagini recente » Cod sursa (job #269933) | Cod sursa (job #125882) | Cod sursa (job #543546) | Cod sursa (job #292898) | Cod sursa (job #1114536)
#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;
};
struct segment {
punct a; punct b;
};
punct p0, p1, p2, p3, p4, p[120000], s[120000];
int n;
int varf;
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(6) << 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, j; int poz = 1;
for (i = 1; i <= n; i++){
if (p[poz].x > p[i].x)
poz = i;
}
for (i = 1; i <= n; i++)
if (p[poz].x == p[i].x and p[poz].y > p[i].y)
poz = i;
punct aux = p[1]; p[1] = p[poz]; p[poz] = aux;
for (i = 2; i < n; i++)
for (j = i + 1; j <= n; j++)
if (prod(p[1], p[i], p[j]) > 0) {
aux = p[i]; p[i] = p[j]; p[j] = aux;
}
// afisn();
varf = 2; s[1] = p[1]; s[2] = p[2];
for (int i = 3; i <= n; ++i) {
while (varf >= 2 && prod(s[varf - 1], s[varf], p[i]) > 0)
--varf;
s[++varf] = p[i];
}
afis();
}
int main() {
fin >> n; int i;
for (i = 1; i <= n; i++)
fin >> p[i].x >> p[i].y;
infas();
}