ホームに戻る
TopCoder の傾向と対策５（Ｃ＋＋編：幾何）
０、はじめに
幾何の問題についていろいろ書いていきます。
幾何は座標や図形を利用して出題される問題のこと。
幾何の問題はたまにでるが全く手が出ないのはもったいない。
難解な公式を知らないと解けないというような問題は出ない。
double の誤差対策、内積、外積、３分探索、平面走査法など、
知っているだけで手を出せる問題が少なくない。
１、図形の性質を用いて答える問題
２、図形の性質を用いて他の解法へ導く問題
３、double で計算結果を求める問題
１は例えば条件を満たす三角形の数を求める、など
２は図形の条件からグラフや動的計画法に持ち込む、など
３はそのまま数値計算や３分探索で値を求める、など
１、小数の誤差の対策
float や double で数値を扱うときほとんどの場合に誤差がある。
printf("%0.20f", 0.3);
と書いたとき表示されるのは、
0.29999999999999998890
である。
これを「丸め誤差」という。
よって、
if(0.1 + 0.2 == 0.3){
printf("OK");
}
この結果は OK を表示しない場合がある。
これは 0.1 や 0.2 や 0.3 がそれぞれ実際には誤差を含んでいることによる。
0.1 + 0.2 == 0.3 の評価法は後で説明する。
float や double を使う以上、精度には限界がある。
また、
double a = 0.0000000000000001;
double b = 1.0000000000000000;
double d = a + b;
この答えは a の値が無視されて 0 になる。
これは 1.0000000000000001 の時点で精度が足らなくなり、
1.000000000000000 とみなされてしまうことによる。
これを「情報落ち」という。
この場合の対処法は計算をできるだけ小さい数字から行うこと。
小さい数字からいきなり大きな数を足すと情報落ちが発生するので、
できるだけ小さい数字から足していき情報落ちを最小にする。
また、
double a = 0.1111111123;
double b = 0.1111111000;
double d = a - b;
この答えは 0.00000001229999999075 となり正確なのは最初の２桁だけになる。
似通った数値で引き算を行うとおきるこの精度落ちを「桁落ち」という。
この場合の対処法はできるだけ引き算を行わないこと。
基本的に誤差とは「丸め誤差」か「情報落ち」か「桁落ち」のどれかでおこる。
小数の誤差を確実に無くす方法がある。
例えば、x1,x2,y1,y2,r の値が整数で与えられ、
(x1, x2) から (x2, y2) の距離が r かどうかを調べるとき、
if(r == sqrt(pow(x2 - x1, 2.0) + pow(y2 - y1, 2.0))){}
などとするのは非常に危険を伴う。
if(r * r == (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1)){}
としておけば完全に安全といえる。
この場合 r * r などがオーバーフローすることがあるので、
値をあえて long long にしておくなどの対策が必要な場合もある。
double どうしの比較をする場合に次のような方法がある。
まず eps に 1e-9 などの十分に小さい値を入れておく。
（1e-9 とは 10 の -9 乗のことを意味する。）
// 誤差を考慮した a == b のチェック
if(fabs(a - b) < eps){} // fabs は double で絶対値を得る
もしくは、
if(a == 0){
if(fabs(b) < eps){}
}
else{
if(fabs((a-b)/a) < eps){}
}
ただし、この方法を使っても適切で無い場合がある。
a と b は根本的に違う値であるがたまたま eps くらいの差しか無かった場合、
a と b が同じ値とみなされてしまう場合がある。
a b がどのような数字なのかを判断して利用する必要がある。
実際に eps の値を調節することでシステムテストが通ったり落ちたりする。
この方法で万能とは言えない。
まとめ、
もしあたかも小数の比較を行わないといけないような場面があっても、
そこは整数型の比較に直せる場合は誤差が皆無になるので、
int や long long の整数型を用いたほうが良いといえる。
再度書いておくが整数型の比較に直す際のオーバーフローには十分注意する。
もちろん eps を使った小数型の比較が通用する場合もある。
eps を使った比較についていろいろ研究しておくと良いと思う。
さて、答えを double で返す場合にはどうするかを考える。
この場合は必ず double を使わざるを得ない。
まず、問題から許容範囲の誤差を読み取る。
もともと double で全く誤差の無い数値を作るのは不可能なので、
TopCoder の問題中にはどの程度誤差が許されるかが書かれている。
まずは用語の説明。
絶対誤差とは | 真値 - 結果値 | のこと。
相対誤差とは | 真値 - 結果値 | / | 結果値 | のこと。
例えば 1e-9 であれば 10 の -9 乗を基準にした誤差まで許される。
では、double がどの程度誤差を出すか考えてみる。
1 + eps としたとき eps がどれくらい小さいと精度落ちになるか考える。
int i = 0;
double eps = 1.0;
double x = 1.0 + eps;
while(x > 1){
i++;
eps /= 2.0;
x = 1.0 + eps;
}
eps *= 2.0;
printf("eps=2^(%d)", -(i - 1));
このとき eps は 2^(-52) となりこれをマシン・イプシロンという。
eps は epsilon の最初の３文字のこと。
よって、double は 1e-15 くらいの精度はあると考えられる。
long double にすると 2^(-63) で 1e-18 くらいまで精度は上がる
最初はできるだけ整数値で計算していき、
（例えば、小数値を分数の分母、分子で記録するとか）
最終的に答えを返す前に少ない計算で double に変換する。
というのが理想的な答え方だと思う。
もし、与えられる数値が最初から double であれば、
途中で double の計算を行う必要がある。
掛け算、割り算を n 回繰り返すと相対誤差が最大 n * eps になる。
よって最初から double で初めてループで計算を繰り返すと、
誤差がどんどん拡大していく可能性がある。
また、足し算、引き算については、
絶対値の大きな数値から計算していくと桁落ちしやすい。
できるだけ絶対値の小さな値から計算を行うことで精度が上がる。
では、TopCoder は解答の誤差をどのように判定するだろうか？
実際に実験してみた。
絶対誤差、相対誤差のいずれかが 1e-9 未満になるようにする場合。
正解が 1.0 のとき 1.0000000009 を提出しても通る。
正解が 1.0 のとき 1.000000001 を提出すると落とされる。
正解が 2.0 のとき 2.0000000019 を提出しても通る。
正解が 2.0 のとき 2.000000002 を提出すると落とされる。
この結果をみると内部で絶対誤差、相対誤差を計算していると思われる。
経験上、double で答えを返す問題の場合は、
計算式さえ間違っていなければ精度で落ちる可能性は低い。
double の比較ほど怖がる必要は無い。
２、TopCoder での誤差対応の限界
小数型を正確に扱うには限界がある。
なぜなら誤差を解消することはできないからである。
例えば、
複雑な計算を行った結果 ans がちょうど 1 かどうか調べるときに、
誤差はせいぜい 1e-14 ほどにおさまると見積もられるなら、
if(fabs(ans-1) < 1e-14){
cout << "ans is ok!" << endl;
}
と書くのは正解であるように思える。
しかし、
複雑な計算を行った結果 ans が真の値として 1 + 1e-16 であった場合に、
この条件比較を用いると ans がちょうど 1 であると判定してしまう。
これはちょうど比較が 1 に近い数字をすべて通してしまう結果である。
ゆえに、 fabs(ans-1) < 1e-14 の比較はよく考えて使う必要がある。
例えば次のような比較には使っても良いだろう。
２点（Ｘ１，Ｙ１）、（Ｘ２，Ｙ２）があるとき。
各座標の値が -1000000000 から 1000000000 の値をとりうるとき。
傾きはＸ１！＝Ｘ２で、（Ｙ２−Ｙ１）／（Ｘ２−Ｘ１）と書ける。
このとき傾きが 1 ちょうどであるかどうかを判定するとするとき。
1 に非常に近い傾き 1999999999.0/2000000000.0 が発生しうる。
しかし、この真値は 0.9999999995 であり。
誤差 0.9999999995 ± 1e-15 を考慮したとしても、
1 ± 1e-14 の間には入ってこない。
よって次のような比較を書いても正確に動作すると言える。
int x1 = -1000000000;
int x2 = 1000000000;
int y1 = -999999999;
int y2 = 1000000000;
if(fabs((double(y2)-y1)/((double(x2)-x1))-1) < 1e-14)
この例を見るとよっぽどで無いと誤差の間に入ってくることは無さそうに思える。
しかし、以下のような例ではこういった比較のやり方が通用しない。
long long x1 = -1000000000;
long long x2 = 1000000000;
long long y1 = 0;
long long y2 = 1;
if(fabs(sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1)) - 2000000000) < 1e-14)
これは 4000000000000000000 + 1 の計算で + 1 が誤差により無視されることによる。
最大値と最小値を見ながら比較のやり方に穴が無いかを検証する必要がある。
TopCoder は誤差によって正確な答えがあいまいになるような問題は出ない。
確実に答えを導き出せる方法がきっと見つかるはずである。
他に、分母と分子を分けて記録していく方法などでも誤差を回避できる。
double の計算は繰り返すごとに誤差が広がる可能性がある。
分母と分子に分けて計算し、最後に分子から分母を割り算すれば誤差は最小になる。
もちろん、分母での０除算、分子と分母のオーバーフローには気をつけたい。
３、非線形関数の解法
非線形関数は直線で無い曲線の関数。
解の公式を用いずにプログラムで答えを求めることができる。
今回はわかりやすい２分法を用いる。
例では f(x) = x^2 - 2 の解 x の値を求める。
大切なのは求める区間が a < x < b であり解は１つであること。
f(a) < 0、f(b) > 0 であることが重要である。
f(a) > 0、f(b) < 0 の場合もコードを書き換えれば対応できる。
なお、終了条件に f(c) == 0 を使うのは適切では無い。
#define eps 1e-9
double f(double x){
return x * x - 2.0;
}
// a < b, f(a) < 0, f(b) > 0 であること
int main(){
double a = 0.0;
double b = 2.0;
double c;
int count = 0;
for(;;){
count++;
c = (a + b) / 2.0;
if(fabs(f(c)) < eps){
break;
}
if(f(c) > 0)b = c;
if(f(c) < 0)a = c;
}
printf("%.12f(count:%d)\n", c, count);
return 0;
}
４、３分探索
結果が下に凸であるグラフを描くとき最小値を求める。
区間を３つに区切り、区間が a と b (a < b)のとき、
f(a) > f(b) であれば a より右の区間を残す。
f(a) < f(b) であれば b より左の区間を残す。
f(a) == f(b) であればどちらを縮めても良い。
このように a == b になるまで区間を縮めていく。
この原理により下に１つの凸でないと答えはでない。
もちろんＷ型のグラフでは正確に動作しない。
double left = 0.0;
double right = 10000.0;
while(right - left > 1e-12){
double d = (right - left) / 3.0;
double l = f(left + d);
double r = f(right - d);
if(l > r){
left = left + d;
}else{
right = right - d;
}
}
cout << left << endl;
1e-12 は求めるべき答えの許容誤差から調節することができる。
逆に上が凸のときも求めることができる。
５、連立方程式の解法
連立１次方程式はプログラムで解くことができる。
連立方程式を使う問題は幾何以外の問題でもよく出題される。
変数は１次であればいくつあっても良い。
変数の数だけ式が必要になる。
以下の方法はガウスの消去法（もしくは掃きだし法）と呼ぶ。
2x + 3y + 3z = 5
3x + 2y - z = -4
5x + 4y + 2z = 3
のとき初期値を
| 2 3 3 |
a = | 3 2 -4 |
| 5 4 2 |
| 5 |
b = | -4 |
| 3 |
として以下のようにする。
解は x の配列に入る。
#define N 3
int main(){
int i, j, k;
double a[N][N], b[N], x[N], w, m, s;
a[0][0]=2; a[0][1]=3; a[0][2]=3; b[0]=5;
a[1][0]=3; a[1][1]=2; a[1][2]=-1; b[1]=-4;
a[2][0]=5; a[2][1]=4; a[2][2]=2; b[2]=3;
for(k = 0; k < N-1; k++){
w = 1.0 / a[k][k];
for(i = k + 1; i < N; i++){
m = a[i][k] * w;
for(j = k + 1; j < N; j++){
a[i][j] -= m * a[k][j];
}
b[i] -= m * b[k];
}
}
x[N-1] = b[N - 1] / a[N-1][N-1];
for(k = N - 2; k >= 0; k--){
s = 0.0;
for(j = k + 1; j < N; j++){
s += a[k][j] * x[j];
}
printf("%f\n", a[k][k]);
x[k] = (b[k] - s) / a[k][k];
}
for(i = 0; i < N; i++){
printf("x[%d]=%f\n", i, x[i]);
}
return 0;
}
計算量は変数が n 個あれば n^3 で終わる。
６、内積
内積をとることで２線が直角かどうか調べることができる。
工夫すればある２点がある直線を中心に対称かどうかわかる。
例えば直線AB に対して異なる２点C,D の対称を調べるとき、
直線AB と直線CD が直角で AC と AD の距離が等しければ良い。
さらに内積では鋭角か鈍角かの判断もできる。
点座標に整数の値が与えられれば double を使わずに計算できる。
// 内積
// 角BAC が鈍角であれば負の値を返す
// 角BAC が直角であれば 0 を返す
// 角BAC が鋭角であれば正の値を返す
// 計算内部でのオーバーフローに気をつけること
int f(int ax, int ay, int bx, int by, int cx, int cy){
int x1 = (bx-ax);
int y1 = (by-ay);
int x2 = (cx-ax);
int y2 = (cy-ay);
return x1 * x2 + y1 * y2;
}
７、外積
外積を使ってある３点が右回りか左回りかを調べることができる。
右回り 左回り
A C
B
A
C B
上図のように右回り、左回りが存在する。
外積の式に当てはめることで判定を行う。
式に当てはめるとき点ABCを与える順番は重要である。
この方法を応用すれば、線に対して点がどちらにあるか判定できる。
上の例では線ABに対して点Cがどちら側にあるかを判定できる。
さらに応用すると三角形の内部に点が存在するかどうか？
さらに多い多角形の内部に点が存在するか？など調べることができる。
外積が 0 かどうかを調べれば線分上に点が存在するかわかる。
応用すれば２直線が平行であるかどうかもわかる。
点座標に整数の値が与えられれば double を使わずに計算できる。
計算内容が簡単であり、誤差を考えなくても良いので扱いやすい。
// 外積
// 左→右の線AB より 点C が下にあれば負の値を返す
// 左→右の線AB の線上に 点C があれば 0 を返す
// 左→右の線AB より 点C が上にあれば正の値を返す
// 計算内部でのオーバーフローに気をつけること
int f(int ax, int ay, int bx, int by, int cx, int cy){
int x1 = (bx-ax);
int y1 = (by-ay);
int x2 = (cx-ax);
int y2 = (cy-ay);
return x1 * y2 - y1 * x2;
}
線分と線分が交差するかどうかも外積で求めることができる。
線分ABと線分CDの交差を調べるとき、
線分ABに対して点Cと点Dが逆側にあることを調べ、
線分CDに対して点Aと点Bが逆側にあることを調べる。
共に成り立てば線分は交差する。
８、凸包
凸包は複数の点群からいちばん外側の最小数の点を選び、
線で繋いですべての点を囲う方法のこと。
点が線上にあるときにはその点は使わない。
例えば、
点１、２、３の内部に点０があるとき、
点０〜点３を凸包にかけると、
点１→点２→点３→点１などの順番で結果が得られる。
結果は最後に戻るので点の数を数えるときには１つ引く必要がある。
struct Point{
int x, y;
bool operator <(const Point &p) const {
return x < p.x || (x == p.x && y < p.y);
}
};
long long cross(const Point &O, const Point &A, const Point &B){
return (long long)(A.x - O.x) * (B.y - O.y) - (long long)(A.y - O.y) * (B.x - O.x);
}
vector<Point> convex_hull(vector<Point> P){
int chn = P.size();
int chk = 0;
vector<Point> H(2*chn);
sort(P.begin(), P.end());
for(int i = 0; i < chn; i++){
while(chk >= 2 && cross(H[chk-2], H[chk-1], P[i]) <= 0)chk--;
H[chk++] = P[i];
}
for(int i = chn-2, t = chk+1; i >= 0; i--){
while(chk >= t && cross(H[chk-2], H[chk-1], P[i]) <= 0)chk--;
H[chk++] = P[i];
}
H.resize(chk);
return H;
}
９、練習問題１ 交点の数
問題
２つの異なる地点Ａ（Ｘ１，Ｙ１）、Ｂ（Ｘ２，Ｙ２）がある。
ちょうどＡから距離がＲ１、ＢからＲ２である地点はいくつあるか？
Ｘ１、Ｙ１、Ｘ２、Ｙ２は -1000000000 から 100000000 の範囲にある。
Ｒ１、Ｒ２は 1 から 100000000 の範囲にある。
考え方
２つの円の交点の数を求める問題に等しい。
まずＡＢ間の距離を求める。
次にＡＢ間の距離をＲ１、Ｒ２の距離で比較する。
例えば、ＡＢ間の距離とＲ１＋Ｒ２の距離が等しいか調べるとき、
if(sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1)) == r1+r2)
という if 文を書きがちだがこれではアウトになる。
まず、
x1 = -1000000000, y1 = 0, r1 = 1000000000,
x2 = 1000000000, y2 = 0, r2 = 1000000000 で失敗する。
もし x1,x2 が int 型なら (x2-x1)*(x2-x1) でオーバーフローする。
たとえ long long になっていたとしても、
x1 = -1000000000, y1 = 0, r1 = 1000000000,
x2 = 1000000000, y2 = 1, r2 = 1000000000 で失敗する。
これは sqrt した結果がちょうど 2000000000 になっているからである。
本来ならば2000000000より少し長い値であるが誤差で消えてしまう。
この誤差によって０が答えであるはずなのに答え１を返してしまう。
解決策としてすべての値を long long にして以下の比較を行う。
if((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) == (r1+r2) * (r1+r2))
こうすることで double を使わずに比較をすることが可能になる。
このアイデアを利用したのが以下のコードである。
double を使っていないのでそもそも誤差が発生しない。
long long x1 = x1_;
long long y1 = y1_;
long long r1 = r1_;
long long x2 = x2_;
long long y2 = y2_;
long long r2 = r2_;
long long d = (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
if(d == (r1+r2)*(r1+r2))cout << 1 << endl;
else if(d == (r1-r2)*(r1-r2))cout << 1 << endl;
else if(d == (r2-r1)*(r2-r1))cout << 1 << endl;
else if(d > (r1+r2)*(r1+r2))cout << 0 << endl;
else if(d < (r1-r2)*(r1-r2))cout << 0 << endl;
else if(d < (r2-r1)*(r2-r1))cout << 0 << endl;
else cout << 2 << endl;
他の解答として、1e-12 などを利用して、
if(fabs(sqrt(double(d)) - (r1+r2)) < 1e-12)
などの評価を考えるかもしれないが、
この場合も上記の sqrt の誤差を回避することはできない。
要点はこの２つ。
整数型が使えるのであればできるだけ double を使わないこと。
整数型を使うのであればオーバーフローに気をつけること。
１０、練習問題２ 木を揃える
問題
一直線上にＮ本の木がある（最小２本、最大５０本）。
木の位置 X0 から Xn-1 と高さ H0 から Hn-1 がわかっている。
位置は X0 は必ず 0 でその他は最小 1 から最大 1000 まで。
高さは 最小 1、最大 100 である。
例えば、
X:0,2,3
H:1,2,4
であれば 0 の位置に高さ 1 の木があり、
2 の位置に高さ 2、3 の位置に高さ 4 で合計３本の木がある。
このとき最小本数の木を切ってすべての高さを一直線に揃えたい。
この場合の一直線とは必ずしも地面に水平でなくとも良い。
例えば、この例では高さ 4 の木を切って高さ 2.5 にすれば一直線になる。
木は切ることはできるが伸ばすことはできない。
そして、高さを０より小さく切ることはできない。
木の情報が与えられたとき、切る最小の本数はいくらか？
考え方
２本の木を定めてその直線に揃えることを考える。
もし木を伸ばす必要があれば揃えることは不可能である。
もし切るだけで済むのであればその本数を数える。
最小の本数で済む場合を答えとする。
ただし、
X:0,1,2
H:3,1,3
以上のときに２本を定めて高さを揃えることができない。
このような場合は真ん中の１本以外を１の高さに切れば良い。
では木を揃える判定はどのようにすれば良いか？
ここで外積の計算を用いる。
外積を使うとある点が線より上か線上か線より下かを判定できる。
そして何より線と点が整数から与えられたものであれば、
double を使わずに正確に判定することが可能である。
外積は３点から三角形が右回りか左回りかを調べることができる。
すなわち左の点Ａから右の点Ｂに伸びる直線があり、
点Ｃが線ＡＢより下かを調べるには、
三角形ＡＢＣが右周りであることを調べれば良いことになる。
以下の例では外積の計算を利用している。
外積計算を使用することにより。
定めたラインより木の頂上が上か下かちょうどかを調べることができる。
// 外積
// 左→右の線AB より 点C が下にあれば負の値を返す
// 左→右の線AB の線上に 点C があれば 0 を返す
// 左→右の線AB より 点C が上にあれば正の値を返す
// 計算内部でのオーバーフローに気をつけること
int f(int ax, int ay, int bx, int by, int cx, int cy){
int x1 = (bx-ax);
int y1 = (by-ay);
int x2 = (cx-ax);
int y2 = (cy-ay);
return x1 * y2 - y1 * x2;
}
int mn = 100;
for(int i = 0; i < dx.size(); i++){
for(int j = i+1; j < dx.size(); j++){
int up = 0; // 木のラインより上をカウント
int down = 0; // 木のラインより下をカウント
int flag = 1; // 木の高さが負にならないかをチェック
for(t = 0; t < dx.size(); t++){
int ax = dx[i];
int ay = dy[i];
int bx = dx[j];
int by = dy[j];
int cx = dx[t];
int cy = dy[t];
int d1 = f(ax,ay,bx,by,cx,cy);
int d2 = f(ax,ay,bx,by,cx,0);
if(d1 > 0)up++;
if(d1 < 0)down++;
if(d2 > 0)flag = 0;
}
if(down != 0 || flag == 0)continue;
mn = min(mn, up);
}
}
if(mn == 100){
return dx.sz-1;
}
cout << mn << endl;
１１、練習問題３ リボンを繋ぐ
問題
一直線にＮ本の木が立っている（最小２本、最大５０本）。
１本１本の間の距離はちょうど 1 である。
木の高さは最小 2 から最大 100 である。
この木の下から高さ 1 の場所か頂上にリボンをかける。
左から右の木に１本のリボンをたるみ無くつけていったとき、
最長の長さはいくらか？
例えば、
2,100,3
の３本の木があった場合、
1,100,1 の位置でリボンをつけるのが最長になる
答えは sqrt(1 * 1 + 99 * 99) * 2 になる。
考え方
左からリボンをつけていく。
下から繋ぐのか上からつつなぐのか考えて、
長くなるほうを上と下の両方で覚えておく。
これを更新していく。
このケースでは double を使って問題無い。
TopCoder では解答に対してのある程度の計算誤差は許容している。
double の誤差は 1e-15 程度なので、
５０個の加算をしても最悪でも 1e-15 * 50 の誤差しか出ない。
解答の誤差許容は問題に書いてあるので、
例えば 1e-12 くらいの誤差が許容されるのであれば全然問題無い。
こういった場合に誤差の見積もりができると確実である。
double up = 0.0;
double down = 0.0;
for(int i = 1; i < d.size(); i++){
double new_up, new_down;
new_up = max(down + sqrt((d[i]-1) * (d[i]-1) + 1), up + sqrt((d[i]-d[i-1]) * (d[i]-d[i-1]) + 1));
new_down = max(down + 1, up + sqrt((1-d[i-1]) * (1-d[i-1]) + 1));
up = new_up;
down = new_down;
}
cout << max(up,down) << endl;
１２、練習問題４ 重なった紙
問題
四角形の紙がＮ枚ある（最小１枚、最大５０枚）。
紙は２次元平面上にＸ軸、Ｙ軸に平行に置かれている。
(x1,y1)(x2,y2) = (0,0)(3,2) であれば、
縦の長さが 2、横の長さが 3 の紙が左下端を原点にして置かれている。
(x1,y1)は必ず左下、(x2,y2)は必ず右上である。
与えられる数値は整数で最小 0 から 最大 10000 である。
すべての紙の情報が与えられるとき、
最も紙が重なった部分が多い部分は何枚紙が重なっているか？
ただし、(0,0)(1,1)、(1,0)(2,1) など、
端が接しているだけのものは重なったとみなさない。
考え方
考えられるすべての点について四角形の内部かどうかを調べる。
しかし、この方法は 10000×10000×50 で間に合わない。
よって、四角形の左端の座標と下端の座標で総当りをかける。
こうすると 50×50×50 で終了する。
２次元平面上の図形の問題はＸ軸の値で走査してＹ軸の値で評価する、
というような考え方をするとわかりやすいことがある。
座標を全探索できない場合は特徴のある点に注目すると良い。
vector<int> dx;
vector<int> dy;
for(int i = 0; i < n; i++){
dx.pb(x1[i]);
dy.pb(y1[i]);
}
int mx = 1;
for(int x = 0; x < n; x++){
for(int y = 0; y < n; y++){
int c = 0;
int ax = dx[x];
int ay = dy[y];
for(int r = 0; r < n; r++){
if(ax < x1[r] || x2[r] <= ax)continue;
if(y1[y] <= ay && ay < y2[r])c++;
}
mx = max(mx,c);
}
}
cout << mx << endl;
