galsko_selo

Rimljani se spremaju za napada na Galsko selo. Getafiks, Asteriks i Obeliks nisu u selu, a Gali više nemaju zaliha čarobnog napitka. Njihova jedina nada je da izgrade veliki zid oko sela koji bi mogao da ih spase od napada Rimljana. Zid može biti izgrađen samo na nosećim stubovima. Ako su poznate koordinate svake kuće u Galskom selu, kao i koordinate svakog nosećeg stuba, proveriti da li Gali mogu da izgrade zid, tako da zaštite svaku kuću u selu.

Opis ulaza

Sa standardnog ulaza se unose vrednosti \(m\) i \(n\) koje predstavljaju broj kuća i stubova redom. Nakon toga se u narednih \(m\) linija unose po 2 vrednosti koje predstavljaju koordinate svake od kuća, a zatim i \(n\) parova vrednosti koje predstavljaju koordinate nosećih stubova.

Opis izlaza

Na standardni izlaz ispisati \(DA\) ako je moguće izgraditi zid tako da svaka kuća bude bezbedna, odnosno \(NE\) ukoliko to nije moguće.

Primer

Ulaz

Izlaz

Rešenje

Opis glavnog rešenja

Za rešenje zadatka možemo koristiti Grahamov algoritam za određivanje konveksnog omotača \(n\) tačaka. U našem slučaju postoje 2 vrste tačaka, kuće i noseći stubovi. Možemo koristiti enum tip da bismo za svaku tačku pamtili koje je vrste. Sve tačke možemo posmatrati jednako, kao da mogu biti tačke konveksnog omotača (iako se on gradi samo na nosećim stubovima). Kad pronađemo konveksni omotač, ostaje nam da proverimo da li je neka od tačaka koja je teme konveksnog omotača kuća. Ukoliko imamo taj slučaj, nije moguće zaštititi sve kuće u selu, pa je traženo rešenje NE. U suprotnom, odgovor je na pitanje iz zadatka je DA.

Grahamov algoritam prvo pronalazi ekstremnu tačku (onu sa najmanjom y koordinatom, a ako ima više takvih, uzima najlevlju od njih) u linearnoj složenosti. Sledeći korak algoritma je sortiranje svih tačaka A prema uglu koje prava povučena kroz ekstremnu tačku i tačku A zaklapa sa x osom. Ako su tačke kolinearne, sortiraju se prema udaljenosti od ekstremne tačke. Ovaj korak algoritma je složenosti \(O(n \log n)\). Nakon toga u lineranoj složenosti dodajemo tačke u konveksni omotač. Poslednji korak algoritma u konkretnom zadatku je proći kroz sve tačke u konveksnom omotaču (kojih ima \(O(m + n)\)) i proveriti da li je neka od njih kuća. Deo algoritma koji je najveće složenosti je sortiranje svih tačaka (i kuća i stubova), pa je ukupna složenost algoritma \(O((m + n) \log (m + n))\).

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

enum point_type {Pillar, House};

class Point
{
public:
   Point () {}

   Point (int _x, int _y, point_type _type)
   {
      x = _x;
      y = _y;
      type = _type;
   }

   int get_x() const { return x; }
   int get_y() const { return y; }
   point_type get_type() const { return type; }

private:
   int x;
   int y;
   point_type type;
};

// Tacka u odnosu na koju se vrsi sortiranje svih ostalih tacaka po uglu
Point p_0;

int find_extreme_point(vector<Point> &points)
{
   int min_y = points[0].get_y(), min_index = 0, n = points.size();

   for (int i = 1; i < n; i++) {
      int y = points[i].get_y();

      // Trazimo tacku sa najmanjom vrednoscu y koordinate ili najlevlju takvu ako ih ima vise
      if ((y < min_y) || (min_y == y && points[i].get_x() < points[min_index].get_x())) {
         min_y = points[i].get_y();
         min_index = i;
      }
   }

   return min_index;
}

void swap(Point &p_1, Point &p_2)
{
        Point tmp = p_1;
        p_1 = p_2;
        p_2 = tmp;
}

int orientation(const Point &p, const Point &q, const Point &r)
{
        int val = (q.get_y() - p.get_y()) * (r.get_x() - q.get_x()) -
                                                (q.get_x() - p.get_x()) * (r.get_y() - q.get_y());

        if (val == 0)
                return 0;

        return (val > 0) ? 1 : 2;
}

// Ne moramo da imamo koren, jer nama ne treba stvarno rastojanje vec samo njihov odnos, pa ako je sqrt(x) < sqrt(y) vazi i x < y
int distance(const Point &p_1, const Point &p_2)
{
    return (p_1.get_x() - p_2.get_x()) * (p_1.get_x() - p_2.get_x()) + (p_1.get_y() - p_2.get_y()) * (p_1.get_y() - p_2.get_y());
}

bool compare(const Point &p_1, const Point &p_2)
{
  int orient = orientation(p_0, p_1, p_2);

  // suprotno od kretanja kazaljke na satu
  if (orient == 2)
    return true;
  // u smeru kretanja kazaljke na satu
  else if (orient == 1)
    return false;

  // kolinearne
  return distance(p_0, p_1) < distance(p_0, p_2);
}

bool simple_polygon(vector<Point> &points)
{
   int extreme_index = find_extreme_point(points);

   swap(points[0], points[extreme_index]);

   // Sve tacke sortiramo prema uglu u odnosu na ekstremnu tacku
   p_0 = points[0];

   sort(points.begin() + 1, points.end(), compare);

   vector<Point> result;

   result.push_back(points[0]);
   result.push_back(points[1]);

   int n = points.size();
   int m = 1;

   for (int k = 2; k < n; k++) {
      while (result.size() >= 2 && orientation(result[m - 1], result[m], points[k]) != 2) {
         result.pop_back();
         m--;
      }

      m++;
      result.push_back(points[k]);
   }

   for (const Point &p : result) {
      if (p.get_type() == House) {
         return false;
      }
   }

   return true;
}

int main ()
{
   int m, n, x, y;

   cin >> m >> n;

   vector<Point> points;

   for (int i = 0; i < m; i++) {
      cin >> x >> y;
      points.push_back({x, y, House});
   }

   for (int i = 0; i < n; i++) {
      cin >> x >> y;
      points.push_back({x, y, Pillar});
   }

   cout << simple_polygon(points) ? "DA\n" : "NE\n";

   return 0;
}