Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using ld = long double;
- using ull = unsigned long long;
- using pii = pair<int, int>;
- using pll = pair<ll, ll>;
- using pld = pair<ld, ld>;
- #define fi first
- #define se second
- #define pb push_back
- #define pf push_front
- #define mp make_pair
- #define ins insert
- #define btpc __builtin_popcount
- #define btclz __builtin_clz
- #define sz(x) (int)(x.size());
- #define all(x) x.begin(), x.end()
- #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
- int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
- int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
- template<class X, class Y>
- bool minimize(X &x, const Y &y) {
- if (x > y)
- {
- x = y;
- return true;
- }
- return false;
- }
- template<class X, class Y>
- bool maximize(X &x, const Y &y) {
- if (x < y)
- {
- x = y;
- return true;
- }
- return false;
- }
- const int MOD = 1e9 + 7; //998244353
- template<class X, class Y>
- void add(X &x, const Y &y) {
- x = (x + y);
- if(x >= MOD) x -= MOD;
- }
- template<class X, class Y>
- void sub(X &x, const Y &y) {
- x = (x - y);
- if(x < 0) x += MOD;
- }
- /* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/
- const ll INF = 1e4;
- const int N = 55 + 10;
- template <typename T> T mod_inv_in_range(T a, T m) {
- // assert(0 <= a && a < m);
- T x = a, y = m;
- T vx = 1, vy = 0;
- while (x) {
- T k = y / x;
- y %= x;
- vy -= k * vx;
- std::swap(x, y);
- std::swap(vx, vy);
- }
- assert(y == 1);
- return vy < 0 ? m + vy : vy;
- }
- template <typename T> T mod_inv(T a, T m) {
- a %= m;
- a = a < 0 ? a + m : a;
- return mod_inv_in_range(a, m);
- }
- template <int MOD_> struct modnum {
- static constexpr int MOD = MOD_;
- static_assert(MOD_ > 0, "MOD must be positive");
- using ll = long long;
- int v;
- public:
- modnum() : v(0) {}
- modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
- explicit operator int() const { return v; }
- friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
- friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }
- friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
- friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
- modnum inv() const {
- modnum res;
- res.v = mod_inv_in_range(v, MOD);
- return res;
- }
- friend modnum inv(const modnum& m) { return m.inv(); }
- modnum neg() const {
- modnum res;
- res.v = v ? MOD-v : 0;
- return res;
- }
- friend modnum neg(const modnum& m) { return m.neg(); }
- modnum operator- () const {
- return neg();
- }
- modnum operator+ () const {
- return modnum(*this);
- }
- modnum& operator ++ () {
- v ++;
- if (v == MOD) v = 0;
- return *this;
- }
- modnum& operator -- () {
- if (v == 0) v = MOD;
- v --;
- return *this;
- }
- modnum& operator += (const modnum& o) {
- v -= MOD-o.v;
- v = (v < 0) ? v + MOD : v;
- return *this;
- }
- modnum& operator -= (const modnum& o) {
- v -= o.v;
- v = (v < 0) ? v + MOD : v;
- return *this;
- }
- modnum& operator *= (const modnum& o) {
- v = int(ll(v) * ll(o.v) % MOD);
- return *this;
- }
- modnum& operator /= (const modnum& o) {
- return *this *= o.inv();
- }
- friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
- friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
- friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
- friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
- friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
- friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
- };
- using num = modnum<MOD>;
- struct Points {
- int x, y;
- Points operator - (const Points & temp) {
- return {x - temp.x, y - temp.y};
- }
- };
- Points peo[N], kites[N];
- num dp[N][N][N][N];
- int ccw(Points r, Points a, Points b) {
- a = a - r;
- b = b - r;
- int ans = a.x * b.y - a.y * b.x;
- if(ans == 0) return 0;
- if(ans < 0) return -1; //right
- return 1; //left
- }
- bool intersect(Points a, Points b, Points c, Points d) {
- return (ccw(a, b, c) != ccw(a, b, d) && ccw(c, d, a) != ccw(c, d, b));
- }
- int n;
- num f(int l, int r, int lo, int hi) {
- if(l + 1 == r) return 1;
- if(dp[l][r][lo][hi] != 10072005) return dp[l][r][lo][hi];
- num &res = dp[l][r][lo][hi];
- res = 0;
- int cut = -1;
- for(int i = 1; i <= n; i++) {
- if(kites[i].y <= min(kites[lo].y, kites[hi].y) && i != lo && i != hi && !intersect(peo[r], kites[hi], peo[r - 1], kites[i]) && !intersect(peo[l], kites[lo], peo[l + 1], kites[i])) {
- cut = i;
- break;
- }
- }
- if(cut == -1) return res = 0;
- for(int i = l + 1; i < r; i++) {
- res += f(l, i, lo, cut) * f(i, r, cut, hi);
- }
- return res;
- }
- void solve() {
- cin >> n;
- for(int i = 1; i <= n; i++) {
- int x; cin >> x;
- peo[i] = {x, 0};
- }
- sort(peo + 1, peo + 1 + n, [&](Points x, Points y) {
- return x.x < y.x;
- });
- for(int i = 1; i <= n; i++) {
- int x, y; cin >> x >> y;
- kites[i] = {x, y};
- }
- sort(kites + 1, kites + 1 + n, [&](Points x, Points y) {
- return x.y > y.y;
- });
- for(int i = 0; i <= n + 1; i++) {
- for(int j = i; j <= n + 1; j++) {
- for(int l = 0; l <= n + 1; l++) {
- for(int r = 0; r <= n + 1; r++) {
- dp[i][j][l][r] = 10072005;
- }
- }
- }
- }
- peo[0] = {-INF, 0};
- peo[n + 1] = {INF, 0};
- kites[0] = {-INF, INF};
- kites[n + 1] = {INF, INF};
- cout << f(0, n + 1, 0, n + 1);
- }
- int main()
- {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- //online
- #endif
- int tc = 1, ddd = 0;
- // cin >> tc;
- while(tc--) {
- //ddd++;
- //cout << "Case #" << ddd << ": ";
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement