AtCoder ABC #016 : Python練習編

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 - 友達の友達

友人関係が無向グラフの形で与えられる。
各人における、友人の友人である人の数を答えよ。
本人および友人は、友人の友人に含めない。

友人同士を距離１の辺がつないでいると考え、Warshall-Floyedで人同士の距離を求める。
最短距離が２となる間柄が友人の友人である。

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 - 一刀両断

２次元座標において、１つの線分と１つの多角形が与えられる。
線分で多角形を分割すると、何個の要素に分けられるか。
なお、線分の端点は多角形外にある。

線分と辺が２か所交差すると図形が１回分割されるので、線分と辺の交差判定を行い、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)