제출 #1151208

#제출 시각아이디문제언어결과실행 시간메모리
1151208pudelosMixture (BOI20_mixture)C++20
13 / 100
2096 ms676 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, a, b) for(int i=a; i<=b; ++i)
#define sz(A) (int)(A.size())
#define eb emplace_back
#define pb push_back
#define pi pair<int, int>
#define f x
#define s y
#define rs resize
#define V vector


struct Ulamek {
  int a, b;

  Ulamek (int licznik, int mianownik) : a(licznik), b(mianownik) {
    int nwd = __gcd(a, b);
    a/=nwd;
    b/=nwd;
  };
  
  Ulamek operator + (const Ulamek &u) const {
    int licznik = a*u.b + u.a*b;
    int mianownik = u.b*b;
    // int nwd = __gcd(licznik, mianownik);
    // return Ulamek(licznik/nwd, mianownik/nwd);
    return Ulamek(licznik, mianownik);
  }

  Ulamek operator - (const Ulamek &u) const {
    int licznik = a*u.b - u.a*b;
    int mianownik = u.b*b;
    // int nwd = __gcd(licznik, mianownik);
    // return Ulamek(licznik/nwd, mianownik/nwd);
    return Ulamek(licznik, mianownik);
  }

  Ulamek operator * (const Ulamek &u) const {
    int licznik = u.a*a;
    int mianownik = u.b*b;
    // int nwd = __gcd(licznik, mianownik);
    return Ulamek(licznik, mianownik);
  }

  bool operator == (const Ulamek &u) const {
    return (a*u.b == b*u.a);
  }

  bool operator < (const Ulamek &u) const {
    return a*u.b < b*u.a;
  }

  bool operator > (const Ulamek &u) const {
    return !(a*u.b < b*u.a || (a*u.b == b*u.a));
  }
};

struct Punkt {
  Ulamek x, y;
  Punkt (Ulamek a, Ulamek b): x(a), y(b) {}
  bool operator<(const Punkt& p) const {
    if (x < p.x) return true;
    if (x > p.x) return false;
    return y < p.y;
  }
};


V<Punkt> D;
V<bool> del;
multiset<Punkt> punkty;
int n;



Ulamek ccw(Punkt a, Punkt b, Punkt c) {
  a.f=a.f-c.f;
  b.f=b.f-c.f;
  a.s=a.s-c.s;
  b.s=b.s-c.s;
  return (a.f*b.s-b.f*a.s);
}

Ulamek licz_p(int i, int j, int k) {
  Punkt a = D[i];
  Punkt b = D[j];
  Punkt c = D[k];
  Ulamek P = (a.f*(b.s-c.s) + b.f*(c.s-a.s) + c.f*(a.s-b.s));
  if(P.a*P.b<0) {
    if(P.a<0) P.a=-P.a;
    else P.b=-P.b;
  }
  return P;
}

int check() {
  if(punkty.find(D[0])!=punkty.end()) return 1;
  FOR(i, 1, sz(D)-1) FOR(j, 1, sz(D)-1) {
    if(i==j) continue;
    if(del[i] || del[j]) continue;
    if ((min(D[i].f, D[j].f) < D[0].f && D[0].f < max(D[i].f, D[j].f)) ||
        (D[i].f == D[j].f && D[i].f == D[0].f &&
        min(D[i].s, D[j].s) < D[0].s && D[0].s < max(D[i].s, D[j].s))) {
      if (ccw(D[i], D[j], D[0]).a == 0) return 2;
    }

  }

  // FOR(i, 1, sz(D)-1) {
  //   if(del[i]) continue;
  //   FOR(j, i+1, sz(D)-1) {
  //     if(del[j]) continue;
  //     FOR(k, j+1, sz(D)-1) {
  //       if(del[k]) continue;
  //       // if((i==j || i==k) || j==k) continue;
  //       Ulamek pole = licz_p(i, j, k);
  //       if(pole.a==0) continue;
  //       Ulamek P1 = licz_p(i, j, 0);
  //       Ulamek P2 = licz_p(0, k, i);
  //       Ulamek P3 = licz_p(j, 0, k);
  //       if(pole==P1+P2+P3) {
  //         // cout << i << ' ' << j << ' ' << k << '\n';
  //         // cout << D[i].f.a << ' ' << D[i].f.b << ' ' << D[i].s.a << ' ' << D[i].s.b << '\n';
  //         // cout << D[j].f.a << ' ' << D[j].f.b << ' ' << D[j].s.a << ' ' << D[j].s.b << '\n';
  //         // cout << D[k].f.a << ' ' << D[k].f.b << ' ' << D[k].s.a << ' ' << D[k].s.b << '\n';
  //         // // cout << D[i].s << ' ' << D[j].f << ' ' << D[j].s << ' ' << D[k].f << ' ' << D[k].s << '\n';
  //         //     cout << P1.a << ' ' << P1.b << ' ' << '\n';
  //         //     cout << P2.a << ' ' << P2.b << ' ' << '\n';
  //         //     cout << P3.a << ' ' << P3.b << ' ' << '\n';
  //         //     cout << "pole: " << pole.a << ' ' << pole.b << ' ' << '\n';
  //         return 3;
  //       }
  //     }
  //   }
  // }

  return 0;
}

int A, B, C;

signed main() {
  cin.tie(0) -> ios_base::sync_with_stdio(0);
  cin >> A >> B >> C;
  D.pb(Punkt(Ulamek(A, (A+B+C)), Ulamek(B, (A+B+C))));
  cin >> n;
  del.rs(n+1);

  // int cnt=0;
  char typ;
  int trojkaty=0;
  int a, b, c;
  FOR(_, 1, n) {
    cin >> typ;
    if(typ=='A') {
      cin >> a >> b >> c;
      D.pb(Punkt(Ulamek(a, (a+b+c)), Ulamek(b, (a+b+c))));
      FOR(i, 1, sz(D)-2) FOR(j, i+1, sz(D)-2) {
        int k = sz(D)-1;
        if(del[i] || del[j]) continue;
        Ulamek pole = licz_p(i, j, k);
        if(pole.a==0) continue;
        Ulamek P1 = licz_p(i, j, 0);
        Ulamek P2 = licz_p(0, k, i);
        Ulamek P3 = licz_p(j, 0, k);
        if(pole==P1+P2+P3) {
          ++trojkaty;
        }
      }
      punkty.insert(Punkt(Ulamek(a, (a+b+c)), Ulamek(b, (a+b+c))));
    } else {
      int idx;
      cin >> idx;
      del[idx]=1;
      FOR(i, 1, sz(D)-1) FOR(j, i+1, sz(D)-1) {
        if(i==idx || j==idx) continue;
        int k = idx;
        if(del[i] || del[j]) continue;
        Ulamek pole = licz_p(i, j, k);
        if(pole.a==0) continue;
        Ulamek P1 = licz_p(i, j, 0);
        Ulamek P2 = licz_p(0, k, i);
        Ulamek P3 = licz_p(j, 0, k);
        if(pole==P1+P2+P3) {
          --trojkaty;
        }
      }
      punkty.erase(punkty.find(D[idx]));
    }
    int odp = check();
    if(odp==0) {
      if(trojkaty>0) odp=3;
    }
    cout << odp << '\n';
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...