Croc Champ 2012 - Round 2 (Unofficial Div. 2 Edition) - 君はまるで砂漠に咲く、一輪の花。

A. Series of Crimes

brute force,geometry,implementation

ざっくりと大意

・nmの大きさの都市Berlandは3人の犯罪者に狙われている？？
・既に犯罪が行われた3箇所はになっており、4箇所目は先の3箇所と長方形(地図の側と平行)の頂点を形成するでしょう？？

方針のようなもの

・地図の側と平行になる長方形を形成するのに先の3箇所がかなり単純な座標になるような気がするけど大丈夫かコレ･･･

n,k=map(int,raw_input().split())
l,chk,ans=[],[],[]
for i in range(n):
    l.append(list(raw_input()))
    if l[i].count('*')==1:
        chk.append((i,l[i].index('*')))
    elif l[i].count('*')==2:
        for j in range(k):
            if l[i][j]=='*':
                chk.append((i,j))
a=[chk[0][0],chk[1][0],chk[2][0]]
a.sort()
r=a[1]
a.remove(r); a.remove(r)
b=[chk[0][1],chk[1][1],chk[2][1]]
b.sort()
r=b[1]
b.remove(r); b.remove(r)
print a[0]+1,b[0]+1

ほんとに都合いい座標の地図しか無かった。。。入力受け取りながら*の3箇所の座標保存して、それぞれx,y座標が1個(4箇所目になるべき座標)と2個(既に同じ線上に揃ってしまっている)に分けられるので1個の方の座標をx,yで組合せて出力。

B. Number of Triplets

ざっくりと大意

・複数の座標が与えられて、3つを組合せ(A,B,C)でBがA,Cの中点になっているような組合せが幾つあるか？？

方針のようなもの

・2つの座標を選んでその中点となる座標が座標リストの中にあるか？だと時間が全然間に合わなかった

#test 7でTLE
n=int(raw_input())
ans=0
l=[]
for i in range(n):
    x,y=map(int,raw_input().split())
    l.append((x,y))
l.sort()
for i in xrange(n-2):
    for j in xrange(i+2,n):
        x=l[i][0]+l[j][0]
        y=l[i][1]+l[j][1]
        if x%2==0 and y%2==0:
            if (x/2,y/2) in l:
                ans+=1
print ans

test 7がnの最大の3000件分のデータだからここを越えられれば他も通るんじゃないかな