ABC016に参加。
Dの1WAが痛い…。
http://abc016.contest.atcoder.jp/assignments
A - 12月6日
月日が与えられるので、月が日で割り切れるか答えよ。
指示通り割るだけ。
M,D=map(int,raw_input().strip().split(" ")) if M % D == 0: print "YES" else: print "NO"
B - A±B Problem
A,B,Cが与えられる。
A+B=CとA-B=C、どれが成立するかもしくはどれも成立しないか答えよ。
B==0の場合、A==Cならどちらも成立し、A!=Cならどちらも成立しない。
B!=0ならA+B!=A-Bなので、どちらか成立する方があればそれを答えればよい。
B==0の場合分けをせず、足すと引くの場合がそれぞれ成立するか判定してもよい。
A,B,C=map(int,raw_input().strip().split(" ")) if B==0: if A==C: print "?" else: print "!" else: if A-B == C: print "-" elif A+B == C: print "+" else: print "!"
C - 友達の友達
友人関係が無向グラフの形で与えられる。
各人における、友人の友人である人の数を答えよ。
本人および友人は、友人の友人に含めない。
友人同士を距離1の辺がつないでいると考え、Warshall-Floyedで人同士の距離を求める。
最短距離が2となる間柄が友人の友人である。
N,M=map(int,raw_input().strip().split(" ")) mat = [[10000 for i in range(N)] for j in range(N)] for i in range(N): mat[i][i] = 0 for i in range(M): A,B=map(int,raw_input().strip().split(" ")) mat[A-1][B-1] = mat[B-1][A-1] = 1 for i in range(N): for x in range(N): for y in range(N): mat[x][y] = min(mat[x][y], mat[x][i]+mat[i][y]); for i in range(N): cnt = 0 for x in range(N): if mat[i][x] == 2: cnt += 1 print cnt
D - 一刀両断
2次元座標において、1つの線分と1つの多角形が与えられる。
線分で多角形を分割すると、何個の要素に分けられるか。
なお、線分の端点は多角形外にある。
線分と辺が2か所交差すると図形が1回分割されるので、線分と辺の交差判定を行い、1+交差数/2が答えとなる。
分割する線分と、多角形の辺を成す線分の交差判定は外積の符号チェックで行える。
def test(X1,Y1,X2,Y2): x1 = X1-MX1 x2 = X2-MX1 x3 = MX2-MX1 y1 = Y1-MY1 y2 = Y2-MY1 y3 = MY2-MY1 if (y3*x1-x3*y1)*(y3*x2-x3*y2)>=0: return 0 x1=MX1-X1 x2=MX2-X1 x3=X2-X1 y1=MY1-Y1 y2=MY2-Y1 y3=Y2-Y1 if (y3*x1-x3*y1)*(y3*x2-x3*y2)>=0: return 0 return 1 MX1,MY1,MX2,MY2=map(int,raw_input().strip().split(" ")) N=input() X=[] Y=[] for i in range(N): x,y=map(int,raw_input().strip().split(" ")) X.append(x) Y.append(y) cnt = 0 for i in range(N): cnt += test(X[i], Y[i], X[(i+1)%N], Y[(i+1)%N]) print (1+cnt/2)