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 };

struct Point
{
    int x;
    int y;
    point_type type;
};

double orientation(const Point &A, const Point &B, const Point &C) 
{
    return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}

double distance(const Point &A, const Point &B) 
{
    double dx = B.x - A.x;
    double dy = B.y - A.y;

    return dx * dx + dy * dy;
}

void polar_sort(vector<Point> &points)
{
    auto max = 
        max_element(
            begin(points), end(points),
            [](const Point& p1, const Point& p2) {
                return p1.x < p2.x || (p1.x == p2.x && p1.y > p2.y);
            }
        );

    swap(*begin(points), *max);
    const Point& p0 = points[0];

    sort(
        next(begin(points)), end(points),
        [p0](const Point& p1, const Point& p2) {
            auto o = orientation(p0, p1, p2);
            if (o > 0) {
                return true;
            } else if (o < 0) {
                return false;
            }
            return distance(p0, p1) <= distance(p0, p2);
        }
    );
}

bool convex_hull_pillar(vector<Point> &points)
{
    polar_sort(points);

    vector<Point> CH;

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

    const int n = points.size();

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

    for (const Point &p : CH) {
        if (p.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});
   }

   if (convex_hull_pillar(points)) {
       cout << "da" << endl;
   } else {
       cout << "ne" << endl;
   }

   return 0;
}