torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

Codeforces 161, B : Squares

概要

二次元平面上に、n 個の相異なる正方形がある。
n 項からなる数列 a が与えられ、各正方形の一つの対角線の端点の座標は、( \quad 0, \quad 0 \quad )( \quad a_i, \quad a_i \quad ) である。
また、平面上の点について、「正方形の内部にある」とは、正方形の内部または辺上に存在するときであるとする。
丁度 k 個の正方形に含まれる平面上の点の座標を一つ出力せよ。
存在しない場合は -1 を出力せよ。

解法

存在しない場合は、k が n を超える場合です。
また、存在する場合、外側から数えて k 番目の正方形の辺上の点を適当に出力すればよいです。
角の点でも良いので、( \quad a_{ n - k }, \quad a_{ n - k } \quad ) としました。

コード

import Control.Applicative
import Control.Monad
import Data.List

main = do
	[ n, k ] <- map read . words <$> getLine
	as <- reverse . sort . map read . words <$> getLine
	let
		tmp = show $ solve k as
		res = if tmp == "-1" then "-1" else tmp ++ " " ++ tmp
	putStrLn res

solve :: Int -> [Int] -> Int
solve k as
	| k == 0 = ( as !! 0 ) + 1
	| length as < k = -1
	| otherwise = as !! ( k - 1 )