Pagini recente » Cod sursa (job #676538) | Cod sursa (job #95575) | Cod sursa (job #1322912) | Cod sursa (job #1006897) | Cod sursa (job #2551544)
#include <algorithm>
#include <iomanip>
#include <fstream>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct punct{
float x, y;
}p[120001];
int nrPctInfasConv = 0;
punct raspuns[120001];
int ind = 0;
punct SemiplanulStang[100001], SemiplanulDrept[100001];
int ind1 = 0, ind2 = 0;
punct pctStanga, pctDreapta;
void calculSemiplan(punct p){
//calculam determinantul triunghiului format de dr formata de pctStranga si pctDreapta si punctul dat ca param
//si dupa putem decide in ce semiplan se afla punctul fata de dreapta form din pctStanga si pctDreapta
double det = pctStanga.x*pctDreapta.y + pctDreapta.x*p.y + pctStanga.y*p.x - p.x*pctDreapta.y - pctStanga.x*p.y - pctDreapta.x*pctStanga.y;
if(det < 0){ //atunci apartine semiplnului drapta sau jos
SemiplanulDrept[++ind1] = p;
}
if(det > 0){ //atunci apartine semiplnului stanga sau sus
SemiplanulStang[++ind2] = p;
}
}
int comp1(punct a, punct b){
if(a.x < b.x){
return 1;
}
else if(a.x == b.x && a.y < b.y){
return 1;
}
return 0;
}
punct st[100001];
int k;
void InfasuratoareStanga(){
st[0] = pctStanga;
st[1] = SemiplanulStang[1];
k = 1;
for(int i = 2; i <= ind2; i++){
punct p = SemiplanulStang[i];
double det = st[k].x*st[k-1].y + st[k-1].x*p.y + st[k].y*p.x - p.x*st[k-1].y - st[k].x*p.y - st[k-1].x*st[k].y;
if(det > 0){ //dc pct se afla in dr sau jos
k++;
st[k] = p;
}else{
st[k] = p;
}
}
}
void InfasuratoareDreapta(){
st[1] = pctStanga;
st[2] = SemiplanulDrept[1];
k = 2;
for(int i = 2; i <= ind1; i++){
punct p = SemiplanulDrept[i];
double det = st[k].x*st[k-1].y + st[k-1].x*p.y + st[k].y*p.x - p.x*st[k-1].y - st[k].x*p.y - st[k-1].x*st[k].y;
if(det < 0){ //dc pct se afla in dr sau jos
k++;
st[k] = p;
}else{
st[k] = p;
}
}
st[++k] = pctDreapta;
}
int main() {
int n;
in >> n;
int a, b;
//initializam pct stg si dr
pctStanga.x = 1000000001;
pctDreapta.x = -1000000001;
for(int i = 1; i <= n; i++){
in >> p[i].x >> p[i].y;
if(p[i].x < pctStanga.x){
pctStanga = p[i];
}
else if(p[i].x == pctStanga.x && p[i].y < pctStanga.y){
pctStanga = p[i];
}
if(p[i].x > pctDreapta.x){
pctDreapta = p[i];
}
else if(p[i].x == pctDreapta.x && p[i].y > pctDreapta.y){
pctDreapta = p[i];
}
}
//grupam punctele pe semiplane
for(int i = 1; i <= n; i++){
if((p[i].x != pctStanga.x || p[i].y != pctStanga.y) && (p[i].x != pctDreapta.x || p[i].y != pctDreapta.y)){ //dc pct curent nu e nici pct cel mai din stanga si nici pct cel mai din dreapta
calculSemiplan(p[i]);
}
}
//sortam dupa x
sort(SemiplanulDrept + 1, SemiplanulDrept + ind1, comp1);
sort(SemiplanulStang + 1, SemiplanulStang + ind2, comp1);
// for(int i = 1; i <= ind1; i++){
// out << SemiplanulDrept[i].x <<" "<< SemiplanulDrept[i].y <<'\n';
// }
//
// out <<'\n';
// for(int i = 1; i <= ind2; i++){
// out << SemiplanulStang[i].x <<" "<< SemiplanulStang[i].y <<'\n';
// }
InfasuratoareStanga();
nrPctInfasConv += k;
for(int i = k; i >= 1; i--){
raspuns[++ind] = st[i];
}
InfasuratoareDreapta();
nrPctInfasConv += k;
for(int i = 1; i <= k; i++){
raspuns[++ind] = st[i];
}
out << nrPctInfasConv<<'\n';
out <<setprecision(6) << fixed;
for(int i = 1; i <= ind; i++){
out << raspuns[i].x <<' '<< raspuns[i].y <<'\n';
}
}