結果
| 問題 | No.202 1円玉投げ |
| ユーザー |
 niyarin
|
| 提出日時 | 2016-10-04 18:44:42 |
| 言語 | PyPy2 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,614 bytes |
| コンパイル時間 | 171 ms |
| コンパイル使用メモリ | 77,572 KB |
| 実行使用メモリ | 110,736 KB |
| 最終ジャッジ日時 | 2023-08-23 23:29:09 |
| 合計ジャッジ時間 | 12,918 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
ソースコード
N = input()
inputs = [map(int,raw_input().split(" ")) for i in range(N)]
class AABB:
def __init__(self):
pass
def marge(ab1,ab2):
ret = AABB()
ret.left = min(ab1.left,ab2.left)
ret.right = max(ab1.right,ab2.right)
ret.up = min(ab1.up,ab2.up)
ret.down = max(ab1.down,ab2.down)
ret.children = [ab1,ab2]
return ret
def nyrn(self,x,y):
self.left = x - 10
self.right = x + 10
self.up = y - 10
self.down = y + 10
self.x = x
self.y = y
self.children = -1
def search(self,cx,cy):
if cx+10 > self.left and cx-10 < self.right:
if cy-10<self.down and cy+10 > self.up:
if self.children == -1:
return (self.x-cx)**2+(self.y-cy)**2 < 400
else:
for c in self.children:
if c.search(cx,cy):
return True
aabb = AABB()
aabb.nyrn(inputs[0][0],inputs[0][1])
ans = 1
nyrns = [[] for i in range(17)]
nyrns[0].append(aabb)
for x,y in inputs[1:]:
flag = False
for i in range(17):
for c in nyrns[i]:
if c.search(x,y):
flag = True
if flag:
pass
else:
ans+=1
new_aabb = AABB()
new_aabb.nyrn(x,y)
nyrns[0].append(new_aabb)
for i in range(17):
while len(nyrns[i] )>2:
xx = nyrns[i].pop(0)
yy = nyrns[i].pop(0)
zz = AABB.marge(xx,yy)
nyrns[i+1].append(zz)
print ans