Explanation of Inclusion-Exclusion Logic for 1904A
Difference between en1 and en2, changed 638 character(s)
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
    ios::sync_with_stdio(false);↵
    cin.tie(NULL);↵
    int t;↵
    cin >> t;↵
    while (t--) {↵
        long long a, b;↵
        cin >>a a >> b;↵
        pair<long long, long long>k;↵
        pair<long long,long long> k, q;↵
        cin >> k.first >> k.second;↵
        cin >> q.first >> q.second;↵
        set<pair<long long, long long>>w;↵
        set<pair<long long,long long>> w, e;↵
        vector<long long>x= x = {-a, -b, b, a};↵
        vector<long long> y1= = {b, a, a, b};↵
        vector<long long> y2= = {-b, -a, -a, -b};↵
        int count= = 0;↵
↵
        // for the king interceptions↵
↵
        //upper side↵
        for (int i=0;i< = 0; i < 4; i++) {↵
            w.insert({k.first+ + x[i], k.second+ + y1[i]});↵
        }↵
        //lowerside↵
        forfor (int i=0;i< = 0; i < 4; i++) {↵
            w.insert({k.first+ + x[i], k.second+ + y2[i]});↵
        }↵
        int countK= = w.size();↵
↵
        // for the queen interceptions↵
↵
        //upper side↵
        for (int i=0;i< = 0; i < 4; i++) {↵
            e.insert({q.first+ + x[i], q.second+ + y1[i]});↵
            w.insert({q.first+ + x[i], q.second+ + y1[i]});↵
↵
        }↵
        //lowerside↵
        forfor (int i=0;i< = 0; i < 4; i++) {↵
            e.insert({q.first+ + x[i], q.second+ + y2[i]});↵
            w.insert({q.first+ + x[i], q.second+ + y2[i]});↵
        }↵
        int countQ= = e.size();↵
        count= = w.size()- - countK;↵
        cout << countQ- - count << endl;↵
    }↵
    return 0;↵
}↵
↵
```↵
↵
### Explanation of Inclusion-Exclusion Logic↵
↵
I attempted an inclusion-exclusion approach using set sizes:↵
↵
1. **King Attack Positions:** First, I insert all valid attack positions of the King into a set w`w`. The size of this set (`countK = w.size()`) gives us the number of unique positions that can attack the King.↵
↵
2. **Queen Attack Positions:** Next, I create a separate set e`e` to store all valid attack positions of the Queen. The size of e`e` (`countQ = e.size()`) represents the number of unique positions that can attack the Queen independently.↵
↵
3. **Union of Positions:** While inserting the Queen's positions into e`e`, I also insert them into w`w`. Now, w`w` contains the union of attack positions for both the King and the Queen.↵
↵
 ($K \cup Q$).↵
4. **Unique to Queen:** The difference `count = w.size() &mdash;- countK` gives the number of new unique attack positions added by the Queen that were not already in w`w` (i.e., positions that attack only the Queen and not the King).↵
↵
5. **Intersection:** Finally, subtracting `count` from `countQ` (`countQ &mdash;- count`) gives the number of Queen attack positions that overlapped with the King's positions—which represents the exact number of positions that attack both pieces simultaneously (the intersection$K \cap Q$).↵
↵
~~~---↵
↵
### 集合の要素数を用いた包除原理によるアプローチ (Inclusion-Exclusion Approach using Set Sizes)↵
↵
1. まず、キングを攻撃できるすべての有効な位置を集合 w`w` に挿入します。この集合のサイズ（`countK = w.size()`）は、キングを攻撃できるユニークな位置の数を表します。↵
↵
2. 次に、クイーンを攻撃できるすべての有効な位置を格納するための別の集合 e`e` を作成します。e`e` のサイズ（`countQ = e.size()`）は、キングとは独立してクイーンを攻撃できるユニークな位置の数を表します。↵
↵
3. クイーンの位置を e`e` に挿入すると同時に、w`w` にも挿入します。これにより、w`w` はキングとクイーンの両方の攻撃位置の和集合（Union）となります。↵
↵
4. 差分である `count = w.size() &mdash;- countK` は、w`w` にまだ存在しなかった（つまりキングは攻撃せず、クイーンのみを攻撃する）クイーンによって新たに追加されたユニークな攻撃位置の数を表します。↵
↵
5. 最後に、`countQ` から `count` を引く（`countQ &mdash;- count`）ことで、キングの位置と重複したクイーンの攻撃位置の数が得られます。これが両方の駒を同時に攻撃できる位置の正確な数（積集合 / Intersection）となります。

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English DokjaKim 2026-10-07 16:41:59 638
en1 English DokjaKim 2026-10-07 16:40:08 3105 Initial revision (published)