Submission #543595

#	Time	Username	Problem	Language	Result	Execution time	Memory
543595		jacynkaa	Tri (CEOI09_tri)	C++17	100 / 100	610 ms	65536 KiB

tri

#include <bits/stdc++.h>
#include <chrono>
#include <math.h>
using namespace std;
#define endl "\n"
#define mp make_pair
#define st first
#define nd second
#define pii pair<int, int>
#define pb push_back
#define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10), cin.tie(0), cout.tie(0);
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FWD(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define fwd(i, a, b) for (int i = (a); i < (b); ++i)
#define all(c) (c).begin(), (c).end()
#define sz(X) (int)((X).size())
#ifdef LOCAL
ostream &operator<<(ostream &out, string str) {
   for (char c : str)
      out << c;
   return out;
}
template <class L, class R> ostream &operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.st << ", " << p.nd << ")"; }
template <class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
   out << '{';
   for (auto it = a.begin(); it != a.end(); it = next(it))
      out << (it != a.begin() ? ", " : "") << *it;
   return out << '}';
}
void dump() { cerr << "\n"; }
template <class T, class... Ts> void dump(T a, Ts... x) {
   cerr << a << ", ";
   dump(x...);
}
#define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#define debug(...)                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     \
   {}
#endif

//#define int long long
typedef double ld;

namespace CNT {
   struct Line {
      mutable ld k, m, p;
      bool operator<(const Line &o) const { return k < o.k; }
      bool operator<(ld x) const { return p < x; }
   };
   struct LineContainer : multiset<Line, less<>> {
      // ( for doubles , use i n f = 1/.0 , div (a , b) = a/b)
      const double inf = 1 / .0;
      ld div(ld a, ld b) { // floored division
         return a / b;
      }
      bool isect(iterator x, iterator y) {
         if (y == end()) {
            x->p = inf;
            return false;
         }
         if (x->k == y->k)
            x->p = x->m > y->m ? inf : -inf;
         else
            x->p = div(y->m - x->m, x->k - y->k);
         return x->p >= y->p;
      }
      void add(ld k, ld m) {
         auto z = insert({k, -m, 0}), y = z++, x = y;
         while (isect(y, z))
            z = erase(z);
         if (x != begin() && isect(--x, y))
            isect(x, y = erase(y));
         while ((y = x) != begin() && (--x)->p >= y->p)
            isect(x, erase(y));
      }
      pii query(ld x) {
         assert(!empty());
         auto l = *lower_bound(x);
         return mp(l.k, -l.m);
      }
   };
} // namespace CNT

namespace GEO {

   typedef long double K;

   const K EPS = 1e-9;
   struct xy { // punkt w 2D
      K x, y;
      xy(K xi, K yi) : x(xi), y(yi) {}
      xy(pii X) : x(X.st), y(X.nd) {}
      xy() {}
      K norm() const { return x * x + y * y; } // kwadrat(!) normy euklidesowej
      pii getP() { return {x, y}; }
   };
   typedef xy P;
   xy operator+(xy a, xy b) { return xy(a.x + b.x, a.y + b.y); }
   xy operator-(xy a, xy b) { return xy(a.x - b.x, a.y - b.y); }
   xy operator*(xy a, K f) { return xy(a.x * f, a.y * f); }
   xy operator/(xy a, K f) { return xy(a.x / f, a.y / f); }
   xy cross(xy a) { return xy(-a.y, a.x); } // obrot o 90 stopni
   K operator*(xy a, xy b) { return a.x * b.x + a.y * b.y; }
   K det(xy a, xy b) { return a.x * b.y - b.x * a.y; }
   // mowi czy jak bylismy w X, jestesmy w Y i bedziemy w Z to skrecamy w lewo(right-prawo)
   bool left(xy X, xy Y, xy Z) { return det(Y - X, Z - Y) > EPS; }
   bool right(xy X, xy Y, xy Z) { return det(Y - X, Z - Y) < -EPS; }

   struct line { // prosta {v: n*v=c} (n - wektor normalny)
      P n;
      K c;
      line(P ni, K ci) : n(ni), c(ci) {}
      line() {}
   };
   // Czy punkt lezy na prostej?
   bool on_line(P a, line p) { return fabs(p.n * a - p.c) < EPS; }
   // Prosta przechodzaca przez 2 punkty ccw. Zalozenie: a!=b
   line span(P a, P b) { return line(cross(b - a), det(b, a)); }
   // Symetralna odcinka. Zalozenie: a!=b
   line median(P a, P b) { return line(b - a, (b - a) * (b + a) * 0.5); }
   // Przeciecie 2 prostych
   P intersection(line p, line q) {
      K d = det(p.n, q.n);
      if (fabs(d) < EPS)
         throw "rownolegle";
      return cross(p.n * q.c - q.n * p.c) / d;
   }
   // Prosta rownolegla przechodzaca przez punkt
   line parallel(P a, line p) { return line(p.n, p.n * a); }
   // Prosta prostopadla przechodzaca przez punkt
   line perp(P a, line p) { return line(cross(p.n), det(p.n, a)); }
   // Odleglosc punktu od prostej
   K dist(P a, line p) { return fabs(p.n * a - p.c) / sqrt(p.n.norm()); }
   K dist(P a, P b) {
      P tmp = a - b;
      return sqrt(tmp.x * tmp.x + tmp.y * tmp.y);
   }
   // Rzut prostokatny punktu na prosta
   P proj(P a, line p) { return a + p.n * ((p.c - p.n * a) / p.n.norm()); }

   struct AngleCmp {
      xy root;
      AngleCmp(const xy &root_ = xy(0, 0)) : root(root_) {}
      void makeSure(const xy &a) const { assert(a.x > EPS || a.x < -EPS || a.y > EPS || a.y < -EPS); }
      int hp(const xy &a) const { return a.y < -EPS || (a.y <= EPS && a.x < -EPS); }
      bool operator()(xy a, xy b) const {
         a = a - root;
         makeSure(a);
         b = b - root;
         makeSure(b);
         int cmpHP = hp(a) - hp(b);
         if (cmpHP)
            return cmpHP < 0;
         K d = det(a, b);
         if (d > EPS || d < -EPS)
            return d > 0;
         return a.norm() < b.norm() - EPS;
      }
   };
} // namespace GEO

namespace ST {
#define r1 ((l + r) / 2) // ulatwia branie srodka przedzialu
#define l2 (r1 + 1)      // same
   const int MAXN = 1e5 + 99;
   bool tab[MAXN];
   pair<pii, pii> Z[MAXN];

   bool ans(pii A, pii B, CNT::LineContainer &L, vector<pii> &punkty) {
      int dif_x = (A.st - B.st);
      int dif_y = (A.nd - B.nd);
      debug(A, B, dif_x, dif_y);
      if (dif_x == 0)
         return punkty[0].st <= A.st;
      ld R = ld(dif_y) / ld(dif_x);
      debug(R);
      auto p = L.query(R);
      debug(p);
      return GEO::right(GEO::xy(A), GEO::xy(B), GEO::xy(p));
   }

   struct SegmentTree { // drzewo przedział-przedział (add,sum) nie ma pewnosci ze dziala

      struct content {
         CNT::LineContainer L;
         vector<pii> punkty;
         vector<int> zapytania;
      };

      vector<content> C;
      int size;

      SegmentTree(int x) {
         size = (1 << (32 - __builtin_clz(x)));
         C.resize(size * 2);
      }

      void solve(int i) {
         for (int x : C[i].zapytania) {
            debug(x);
            bool res = ans(Z[x].st, Z[x].nd, C[i].L, C[i].punkty);
            tab[x] = res ? true : tab[x];
         }
         C[i].zapytania.clear();
         C[i].L.clear();
      }

      void solve(vector<pii> &P) {
         rep(i, 2 * size) C[i].zapytania.shrink_to_fit();

         rep(i, sz(P)) {
            C[i + size].punkty.push_back(P[i]);
            C[i + size].L.add(P[i].st, P[i].nd);
            solve(i + size);
         }

         for (int i = size - 1; i > 0; i--) {
            for (auto p : C[2 * i].punkty) {
               C[i].punkty.push_back(p);
               C[i].L.add(p.st, p.nd);
            }
            for (auto p : C[2 * i + 1].punkty) {
               C[i].punkty.push_back(p);
               C[i].L.add(p.st, p.nd);
            }
            sort(all(C[i].punkty));
            solve(i);

            C[2 * i + 1].punkty.clear();
            C[2 * i].punkty.clear();
         }
      }

      void query(int p, int q, int val, int l, int r, int wezel = 1) { // suma na przedzial [p,q]
         if (p > q)
            return;

         if (p == l && q == r) {
            C[wezel].zapytania.push_back(val);
            return;
         }

         query(p, min(r1, q), val, l, r1, 2 * wezel);
         query(max(l2, p), q, val, l2, r, 2 * wezel + 1);
      }

      void query(int p, int q, int val) { query(p, q, val, 0, size - 1); }
   }; // namespace ST
} // namespace ST

int32_t main() {
   _upgrade;
   int k, m;
   cin >> k >> m;

   vector<GEO::xy> V;

   rep(i, k) {
      int x, y;
      cin >> x >> y;
      V.push_back({x, y});
   }
   sort(all(V), GEO::AngleCmp());

   ST::SegmentTree D(k + 1);

   rep(j, m) {
      int x1, y1, x2, y2;
      cin >> x1 >> y1 >> x2 >> y2;
      GEO::xy X1 = {x1, y1};
      GEO::xy X2 = {x2, y2};
      auto q = upper_bound(all(V), X1, GEO::AngleCmp()) - V.begin();
      auto p = upper_bound(all(V), X2, GEO::AngleCmp()) - V.begin();
      if (p == q)
         continue;
      if (p > q) {
         swap(p, q);
         swap(X1, X2);
      }
      q--;
      ST::Z[j] = {X1.getP(), X2.getP()};

      debug(x1, y1, x2, y2, p, q);
      D.query(p, q, j);
   }
   vector<pii> R(k);
   rep(i, k) R[i] = {V[i].x, V[i].y};
   V.clear();

   debug(R);
   D.solve(R);

   rep(i, m) cout << (ST::tab[i] ? "Y" : "N") << endl;
}

Compilation message (stderr)

tri.cpp: In function 'int32_t main()':
tri.cpp:262:20: warning: narrowing conversion of 'x' from 'int' to 'GEO::K' {aka 'long double'} [-Wnarrowing]
  262 |       V.push_back({x, y});
      |                    ^
tri.cpp:262:23: warning: narrowing conversion of 'y' from 'int' to 'GEO::K' {aka 'long double'} [-Wnarrowing]
  262 |       V.push_back({x, y});
      |                       ^
tri.cpp:271:21: warning: narrowing conversion of 'x1' from 'int' to 'GEO::K' {aka 'long double'} [-Wnarrowing]
  271 |       GEO::xy X1 = {x1, y1};
      |                     ^~
tri.cpp:271:25: warning: narrowing conversion of 'y1' from 'int' to 'GEO::K' {aka 'long double'} [-Wnarrowing]
  271 |       GEO::xy X1 = {x1, y1};
      |                         ^~
tri.cpp:272:21: warning: narrowing conversion of 'x2' from 'int' to 'GEO::K' {aka 'long double'} [-Wnarrowing]
  272 |       GEO::xy X2 = {x2, y2};
      |                     ^~
tri.cpp:272:25: warning: narrowing conversion of 'y2' from 'int' to 'GEO::K' {aka 'long double'} [-Wnarrowing]
  272 |       GEO::xy X2 = {x2, y2};
      |                         ^~

• Subtask 1: 100 / 100