Cod sursa(job #2757764)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 6 iunie 2021 13:24:47
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb
#include <algorithm>
#include <complex>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;


vector<complex<double>> v;
int N;


void read()
{
  scanf("%d", &N);
  double a, b;
  for (int i = 0; i < N; ++i) {
    scanf("%lf%lf", &a, &b);
    v.emplace_back(a, b);
  }
}

/** 
| a.x a.y 1 |   | a.x     a.y     1|
| b.x b.y 1 | = | b.x-a.x b.y-a.y 0| = (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y)
| c.x c.y 1 |   | c.x-a.x c.y-a.y 0|
 */

double det(complex<double> a, complex<double> b, complex<double> c) {
  return (b.real() - a.real()) * (c.imag() - a.imag()) -
    (c.real() - a.real()) * (b.imag() - a.imag());
}

void calculateEnvelope(vector<complex<double>> v, vector<complex<double>> *envelope)
{
  complex<double> leftmost = v.front();
  complex<double> rightmost = v.back();
  for (complex<double> p: v)
    if (det(leftmost, rightmost, p) >= 0) {
      while(envelope->size() >= 2 &&
	    det((*envelope)[(int)envelope->size() - 2],
		(*envelope)[(int)envelope->size() - 1],
		p) > 0)
	envelope->pop_back();
      envelope->emplace_back(p);
    }
}

void convexHull()
{
  vector<complex<double>> upper_envelope;
  vector<complex<double>> lower_envelope;
  
  sort(v.begin(),
       v.end(),
       [](const complex<double>& a, const complex<double>& b) {
	 if (a.real() == b.real()) 
	   return a.imag() < b.imag();
	 return a.real() < b.real();
       });
  calculateEnvelope(v, &upper_envelope);  
  reverse(v.begin(), v.end());
  calculateEnvelope(v, &lower_envelope);

  printf("%d\n", (int)upper_envelope.size() + (int)lower_envelope.size() - 2);
  for (int i = (int)upper_envelope.size() - 1; i >= 0; --i)
    printf("%lf %lf\n", upper_envelope[i].real(), upper_envelope[i].imag());
  for (int i = (int)lower_envelope.size() - 2; i >= 1; --i)
    printf("%lf %lf\n", lower_envelope[i].real(), lower_envelope[i].imag());
}

int main()
{
 
  freopen("infasuratoare.in", "r", stdin);
  freopen("infasuratoare.out", "w", stdout);
  
  read();
  convexHull();

  
  return 0;
}