ひとりで勝手にはじめた蟻本読書会 二部グラフの最大マッチング問題 蟻本読書会 の続きです。
3点と三角形の面積
C – 直訴
点 A の座標が (xa , ya)、点 B の座標が (xb , yb)、点 C の座標が (xc , yc) であることを表す。
各座標の値 xa , ya , xb , yb , xc , yc は
-1,000 以上 1,000 以下の整数であることが保証されている
三角形 ABC の面積を 出力してください。入力されるデータ
xa , ya , xb , yb , xc , yc
（ただし、-1000 ≦ xa , ya , xb , yb , xc , yc ≦ 1000）
3点の座標から簡単に面積を求める方法があります。原点と(a,b), (c,d) で構成される三角形の面積は、|ad – bc| / 2 です。あとは公式に代入すれば解を得ることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int x0, y0, x1, y1, x2, y2; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); x0 = vs[0]; y0 = vs[1]; x1 = vs[2]; y1 = vs[3]; x2 = vs[4]; y2 = vs[5]; } // （x0, y0）が原点になるように全体を平行移動させる x1 -= x0; y1 -= y0; x2 -= x0; y2 -= y0; double ans = (double)Math.Abs(x1 * y2 - y1 * x2) / 2; Console.WriteLine(ans); } } |
線分と点の距離
B – アリの高橋くん
アリの高橋くんは凸多角形状の板の上にいます。 高橋くんは向いている方向にまっすぐ歩いていきますが、どの方向を向いているかはわかりません。 高橋くんは板の周囲にたどり着くと落ちてしまいます。 高橋くんの位置と板を構成する凸多角形の頂点の位置が与えられるので、高橋くんが板から落ちるまでに歩く最短の距離を求めてください。位置は全て２次元座標で与えられます。
入力されるデータ
x y
N
x_1 y_1
x_2 y_2
…
x_N y_N（ただし、
x, y は高橋くんがいる位置の座標を表す整数 (-100 ≦ x, y ≦100)
N は 凸多角形の頂点数を表す整数 (3 ≦ N ≦ 10)
x_i y_i は頂点の座標を表す整数 (-100≦ x_i, y_i ≦100)
頂点は反時計回りの順で与えられる ）
高橋くんがいる位置から最短の位置にある線分との距離が求める解となります。線分との距離は直線との距離と異なり、線分を構成する2点とのどちらかとの距離になる場合もあるのですが、この場合は各線分をとおる直線との距離の最小値が求める解となります。
点と直線とのあいだの距離の求め方ですが、線分上の点の片方が原点にくるように全体を平行移動させます。そのあともうひとつの点がX軸上にくるように回転させます。そのあと点のY座標の絶対値をとればこれが直線と点の距離となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int x, y; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); x = vs[0]; y = vs[1]; } int N = int.Parse(Console.ReadLine()); int[] X = new int[N]; int[] Y = new int[N]; for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); X[i] = vs[0]; Y[i] = vs[1]; } double ans = double.MaxValue; for (int i = 0; i < N - 1; i++) ans = Math.Min(ans, GetDistance(x, y, X[i], Y[i], X[i + 1], Y[i + 1])); ans = Math.Min(ans, GetDistance(x, y, X[N - 1], Y[N - 1], X[0], Y[0])); Console.WriteLine(ans); } static double GetDistance(int x, int y, int x1, int y1, int x2, int y2) { x -= x1; y -= y1; x2 -= x1; y2 -= y1; // 点 2 が Y 軸上にある場合は 90度回転させるのではなく、X 座標の絶対値を距離とする if (x2 == 0) return Math.Abs(x); // 回転させる角度を求め、回転させる double angle = - Math.Atan2(y2, x2); double newX = Math.Cos(angle) * x - Math.Sin(angle) * y; double newY = Math.Sin(angle) * x + Math.Cos(angle) * y; return Math.Abs(newY); } } |
線分は交差しているか？
D – 一刀両断
高橋くんは鍛錬の結果、空手チョップで木の板を切断できるようになりました。空手チョップの軌道を表す線分と板の形を表す多角形が与えられるので、板がいくつに切断されたか求めてください。
A_x A_y B_x B_y
N
X_1 Y_1
X_2 Y_2
:
X_N Y_N（ただし、
A_x A_y B_x B_y は線分の端点の座標 （-1000 ≦ A_x, A_y, B_x, B_y ≦ 1000）
N は多角形の頂点数（3 ≦ N ≦ 100）
X_i Y_i は各頂点の座標（-1000 ≦ X_i, Y_i ≦ 1000）多角形の頂点は反時計回りの順で与えられる。
多角形の頂点は線分から0.1以上離れている。
線分の端点は多角形から0.1以上離れている。
線分の端点は多角形の外部にある。
多角形の連続する３頂点が一直線上に並ぶことはない）
条件より、以下のような状態はありえません。
多角形の頂点が木の板を切断する線分上にある。
線分の端点が多角形の辺上にある。
多角形の辺と線分が重なる。
線分の端点が多角形の内部にある。
このような条件で木の板を何個に切断することができるかですが、上記の条件下では、多角形と線分の交点の数を半分にしたものに 1 を足したものになります。
では線分と多角形の辺が交差するかはどうやって判定すればよいのでしょうか？
片方の線分から見てもう一方の線分の端点が左右にある場合は両者は交差していると判断することができます。線分ABから見て線分CDの端点が左右にあるかどうかは三角形の符号付き面積を調べてみればわかります。⊿ABCの符号付き面積と⊿ABDの符号付き面積の符号が異なっている場合は線分ABと線分CDは交差しているとみなすことができます。
原点と（x1, y1）、（x2, y2）で構成される三角形の符号付き面積は S = (x1 * y2 – x2 * y1) / 2 です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int x1, y1, x2, y2; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); x1 = vs[0]; y1 = vs[1]; x2 = vs[2]; y2 = vs[3]; } int N = int.Parse(Console.ReadLine()); int[] X = new int[N]; int[] Y = new int[N]; for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); X[i] = vs[0]; Y[i] = vs[1]; } int crossCount = 0; for (int i = 0; i < N - 1; i++) { if(IsCross(x1, y1, x2, y2, X[i], Y[i], X[i + 1], Y[i + 1])) crossCount++; } if(IsCross(x1, y1, x2, y2, X[N - 1], Y[N - 1], X[0], Y[0])) crossCount++; int ans = crossCount / 2 + 1; Console.WriteLine(ans); } static bool IsCross(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) { // 三角形の符号付き面積の符号からふたつの線分が交差するかどうかを調べる // 問題になるのは符号だけなので × 1 / 2 をしていない long a = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1); long b = (x2 - x1) * (y4 - y1) - (y2 - y1) * (x4 - x1); long c = (x4 - x3) * (y2 - y3) - (y4 - y3) * (x2 - x3); long d = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3); if(a * b < 0 && c * d < 0) return true; else return false; } } |
