ํƒœ๊ทธ ๋ณด๊ด€๋ฌผ: geometry

geometry

ํšŒ์ „ ๋œ ์‚ฌ๊ฐํ˜•์˜ ์น˜์ˆ˜ ๊ฒฐ์ • ์ ˆ๋Œ€๋กœ ๊ทธ๋ฆฌ๋“œ ๊ฒฝ๊ณ„๋ฅผ

์ด ์Šคํƒ ์Šค ๋‹ˆํŽซ ์€ ์น˜์ˆ˜, ์œ„์น˜, ๊ฐ๋„ ๋ฐ ๊ทธ๋ฆฌ๋“œ ์น˜์ˆ˜์— ๋Œ€ํ•œ ๋งค๊ฐœ ๋ณ€์ˆ˜๊ฐ€ ์ง€์ •๋œ ๊ฒ€์€ ์ƒ‰ ๋ฐฐ๊ฒฝ์— ๋ณ„๋ช…์„ ๊ฐ€์ง„ ํฐ์ƒ‰ ์ง์‚ฌ๊ฐํ˜•์„ ๊ทธ๋ฆฝ๋‹ˆ๋‹ค .

<style>html *{font-family:Consolas,monospace}input{width:24pt;text-align:right;padding:1px}canvas{border:1px solid gray}</style><p>grid w:<input id='gw' type='text' value='60'> grid h:<input id='gh' type='text' value='34'> w:<input id='w' type='text' value='40'> h:<input id='h' type='text' value='24'> x:<input id='x' type='text' value='0'> y:<input id='y' type='text' value='0'> &theta;:<input id='t' type='text' value='12'>&deg; <button type='button' onclick='go()'>Go</button></p>Image<br><canvas id='c'>Canvas not supported</canvas><br>Text<br><textarea id='o' rows='36' cols='128'></textarea><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><script>function toCart(t,a,n,r){return{x:t-n/2,y:r/2-a}}function vtx(t,a,n){return{x:n.x+t*Math.cos(a),y:n.y+t*Math.sin(a)}}function sub(t,a){return{x:t.x-a.x,y:t.y-a.y}}function dot(t,a){return t.x*a.x+t.y*a.y}function inRect(t,a,n,r){var e=sub(a,t),o=sub(a,n),l=sub(a,r),i=dot(e,o),v=dot(e,l);return i>0&&i<dot(o,o)&&v>0&&v<dot(l,l)}function go(){var t=parseInt($("#gw").val()),a=parseInt($("#gh").val()),n=parseFloat($("#w").val()),r=parseFloat($("#h").val()),e={x:parseFloat($("#x").val()),y:parseFloat($("#y").val())},o=Math.PI*parseFloat($("#t").val())/180,l=Math.sqrt(n*n+r*r)/2,i=Math.atan2(r,n),v=vtx(l,o+i,e),h=vtx(l,o+Math.PI-i,e),u=vtx(l,o-i,e),x=$("#c");x.width(t).height(a).prop({width:t,height:a}),x=x[0].getContext("2d");for(var s="",c=0;a>c;c++){for(var f=0;t>f;f++)inRect(toCart(f+.5,c+.5,t,a),v,h,u)?(s+="..",x.fillStyle="white",x.fillRect(f,c,1,1)):(s+="XX",x.fillStyle="black",x.fillRect(f,c,1,1));a-1>c&&(s+="\n")}$("#o").val(s)}$(go)</script>

( JSFiddle ๋ฒ„์ „ )

ํ…์ŠคํŠธ ํ‘œํ˜„์€ XX์ด๋ฏธ์ง€์— ๊ฒ€์€ ์ƒ‰ ํ”ฝ์…€์ด์žˆ๋Š” ..๊ณณ ๊ณผ ํฐ์ƒ‰ ํ”ฝ์…€์ด์žˆ๋Š” ๊ณณ๋งˆ๋‹ค ์žˆ์Šต๋‹ˆ๋‹ค. (๊ทธ๋“ค์ด ๊ฒฝ์šฐ ์ฐŒ๊ทธ๋Ÿฌ ์™ธ๋ชจ X์™€ ..)

์Šค ๋‹ˆํŽซ์—์„œ ์ƒ์„ฑ ๋œ ์‚ฌ๊ฐํ˜•์˜ ํ…์ŠคํŠธ ํ‘œํ˜„์„ ์ทจํ•˜๊ณ  ์‚ฌ๊ฐํ˜•์˜ ๋Œ€๋žต์ ์ธ ๋„ˆ๋น„์™€ ๋†’์ด๋ฅผ ์‹ค์ œ ๋„ˆ๋น„์™€ ๋†’์ด์˜ ยฑ 7 % ์ด๋‚ด๋กœ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹ญ์‹œ์˜ค .

ํ”„๋กœ๊ทธ๋žจ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ œ์•ฝ ์กฐ๊ฑด์œผ๋กœ ์Šค ๋‹ˆํŽซ์œผ๋กœ ๊ทธ๋ฆด ์ˆ˜์žˆ๋Š” ๋ชจ๋“  ๊ฐ€๋Šฅํ•œ ์‚ฌ๊ฐํ˜•์„ ํšจ๊ณผ์ ์œผ๋กœ ์ž‘๋™ํ•ด์•ผํ•ฉ๋‹ˆ๋‹ค.

  • ์‚ฌ๊ฐํ˜• ๋„ˆ๋น„์™€ ๋†’์ด๋Š” ์ตœ์†Œ 24์ž…๋‹ˆ๋‹ค.
  • ๊ฒฉ์ž ๋„ˆ๋น„์™€ ๋†’์ด๋Š” ์ตœ์†Œ 26์ž…๋‹ˆ๋‹ค.
  • ์‚ฌ๊ฐํ˜•์€ ์ ˆ๋Œ€๋กœ ๊ทธ๋ฆฌ๋“œ ๊ฒฝ๊ณ„๋ฅผ ๊ฑด๋“œ ๋ฆฌ๊ฑฐ๋‚˜ ๋ฒ—์–ด๋‚˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค.

๋”ฐ๋ผ์„œ ์ž…๋ ฅ ์‚ฌ๊ฐํ˜•์—๋Š” ํšŒ์ „, ์œ„์น˜ ๋ฐ ์น˜์ˆ˜๊ฐ€์žˆ์„ ์ˆ˜ ์žˆ์œผ๋ฉฐ ์œ„์˜ ์„ธ ๊ฐ€์ง€ ์ œ์•ฝ ์กฐ๊ฑด์ด ์ถฉ์กฑ๋˜๋Š” ํ•œ ๊ทธ๋ฆฌ๋“œ์˜ ์น˜์ˆ˜๊ฐ€ ๋‹ฌ๋ผ์งˆ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฒฉ์ž ์น˜์ˆ˜๋ฅผ ์ œ์™ธํ•˜๊ณ  ์Šค ๋‹ˆํŽซ ๋งค๊ฐœ ๋ณ€์ˆ˜๋Š” ๋ถ€ ๋™์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์„ธ๋ถ€

  • ์›์‹œ ํ…์ŠคํŠธ ์‚ฌ๊ฐํ˜•์„ ์ž…๋ ฅ์œผ๋กœ ์‚ฌ์šฉํ•˜๊ฑฐ๋‚˜ ์›์‹œ ํ…์ŠคํŠธ ์‚ฌ๊ฐํ˜•์„ ํฌํ•จํ•˜๋Š” ํŒŒ์ผ์˜ ํŒŒ์ผ ์ด๋ฆ„ (stdin ๋˜๋Š” ๋ช…๋ น ํ–‰์„ ํ†ตํ•ด)์„ ์‚ฌ์šฉํ•˜์‹ญ์‹œ์˜ค. ํ…์ŠคํŠธ ์‚ฌ๊ฐํ˜•์— ์ค„ ๋ฐ”๊ฟˆ ๋ฌธ์ž๊ฐ€ ์žˆ๋‹ค๊ณ  ๊ฐ€์ • ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ํ…์ŠคํŠธ ์‚ฌ๊ฐํ˜•์ด and๊ฐ€ ์•„๋‹Œ ๋‹ค๋ฅธ ๋‘ ๊ฐœ์˜ ์ธ์‡„ ๊ฐ€๋Šฅํ•œ ASCII ๋ฌธ์ž ๋กœ ๋งŒ๋“ค์–ด ์ง„๋‹ค๊ณ  ๊ฐ€์ • ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.X. ์›ํ•˜๋Š” ๊ฒฝ์šฐ. ์ค„ ๋ฐ”๊ฟˆ์€ ์ค„ ๋ฐ”๊ฟˆ์„ ์œ ์ง€ํ•ด์•ผํ•ฉ๋‹ˆ๋‹ค.
  • ์ธก์ • ๋œ ํญ๊ณผ ๋†’์ด๋ฅผ ์ •์ˆ˜๋กœ ์ถœ๋ ฅํ•˜๊ฑฐ๋‚˜ ์–ด๋–ค ์ˆœ์„œ๋กœ stdout์— ๋„์šฐ์‹ญ์‹œ์˜ค (์–ด๋А ๊ฒƒ์ด ์–ด๋–ค ๋งค๊ฐœ ๋ณ€์ˆ˜์™€ ํ•จ๊ป˜ ์‹ค์ œ๋กœ ์–ด๋–ค ๊ฒƒ์ธ์ง€ ๊ฒฐ์ •ํ•˜๋Š” ๋ฐฉ๋ฒ•์ด ์—†๊ธฐ ๋•Œ๋ฌธ์—). ๋ถ„๋ช…ํžˆ์ด ๋‘ ์ฐจ์›์„ ๋ณด์—ฌ์ฃผ๊ณ  ์žˆ์Œ์„ ๋ชจ๋“  ํ˜•์‹์€ ์ข‹์€ ์˜ˆ์ด๋‹ค D1 D2, D1,D2, D1\nD2,(D1, D2) , ๋“ฑ
  • ํ”„๋กœ๊ทธ๋žจ ๋Œ€์‹  ํ…์ŠคํŠธ ์‚ฌ๊ฐํ˜•์„ ๋ฌธ์ž์—ด ๋˜๋Š” ํŒŒ์ผ ์ด๋ฆ„์œผ๋กœ ์‚ฌ์šฉํ•˜์—ฌ ๊ฒฐ๊ณผ๋ฅผ ์ •์ƒ์ ์œผ๋กœ ์ธ์‡„ํ•˜๊ฑฐ๋‚˜ ๋‘ ์š”์†Œ๊ฐ€ ํฌํ•จ ๋œ ๋ฌธ์ž์—ด ๋˜๋Š” ๋ชฉ๋ก / ํŠœํ”Œ๋กœ ๋ฐ˜ํ™˜ํ•˜๋Š” ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ๊ทธ ๊ธฐ์–ต XX๋˜๋Š” ..์ง์‚ฌ๊ฐํ˜•์˜ ํ•˜๋‚˜์˜ โ€˜ํ”ฝ์…€โ€™์ด ์•„๋‹Œ์ด์žˆ๋‹ค.

์˜ˆ

์ „์˜. 1

๋งค๊ฐœ ๋ณ€์ˆ˜ : grid w:60 grid h:34 w:40 h:24 x:0 y:0 ฮธ:12(์Šค ๋‹ˆํŽซ ๊ธฐ๋ณธ๊ฐ’)

์ž…๋ ฅ

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX....XXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX............XXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX........................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX............................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX....................................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..............................................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX..........................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX................................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX..........................................................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX..............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX....................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX............................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX..................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX........................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXX............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXX....XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

์ถœ๋ ฅ ์˜ˆ

  • 40 24
  • 24 40
  • [40.0, 24.0]
  • 42.8, 25.68 (+ 7 %)
  • 37.2, 22.32 (-7 %)

์ „์˜. 2

๋งค๊ฐœ ๋ณ€์ˆ˜ : grid w:55 grid h:40 w:24.5 h:24 x:-10.1 y:2 ฮธ:38.5

์ž…๋ ฅ

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX......XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX..................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXX......................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX............................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..............................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX......................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXX............................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXX................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXX..................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXX......................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX..............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX................................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXX..............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXX..............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXX............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXX......................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXX....................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXX................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXX............................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX......................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..........................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX......................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX..................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXX..........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX......XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

์ถœ๋ ฅ ์˜ˆ

  • 24.0 24.5
  • 25.68 26.215 (+ 7 %)
  • 22.32 22.785 (-7 %)

์ฑ„์ 

๋ฐ”์ดํŠธ ๋‹จ์œ„์˜ ๊ฐ€์žฅ ์งง์€ ์ฝ”๋“œ๊ฐ€ ์ด๊น๋‹ˆ๋‹ค. Tiebreaker๋Š” ์ตœ๊ณ  ํˆฌํ‘œ ๊ฒŒ์‹œ๋ฌผ์ž…๋‹ˆ๋‹ค.



๋‹ต๋ณ€

Matlab, 226 ๋ฐ”์ดํŠธ

์•„์ด๋””์–ด๋Š” ๊ฐ„๋‹จํ•ฉ๋‹ˆ๋‹ค. ๋จผ์ € ์‚ฌ๊ฐํ˜•์ด ์–ผ๋งˆ๋‚˜ ๋งŽ์ด ํšŒ์ „ํ–ˆ๋Š”์ง€ ํ™•์ธํ•œ ๋‹ค์Œ ์‚ฌ๊ฐํ˜•์ด ๋˜‘๋ฐ”๋กœ๋˜๋„๋ก ์ด๋ฏธ์ง€๋ฅผ ์ ์ ˆํ•˜๊ฒŒ ๋Œ๋ฆฝ๋‹ˆ๋‹ค. ๊ทธ๋Ÿฐ ๋‹ค์Œ ํ–‰ ์—ด์˜ ๋ชจ๋“  ํ”ฝ์…€์„ ๋”ฐ๋กœ โ€˜ํ•ฉ๊ณ„โ€™ํ•˜๊ณ  ๋„ˆ๋น„์™€ ๋†’์ด๋ฅผ ๊ฒฐ์ •ํ•˜๊ธฐ ์œ„ํ•ด ํ‰๊ท  (๊ฐ„๋‹จํ•œ ์ž„๊ณ„ ๊ฐ’)๋ณด๋‹ค ๋งŽ์€ ํ•ฉ๊ณ„๋ฅผ ๊ณ„์‚ฐํ•˜์‹ญ์‹œ์˜ค. ์ด ๊ฐ„๋‹จํ•œ ๋ฐฉ๋ฒ•์€ ๋†€๋ž๋„๋ก ์•ˆ์ •์ ์œผ๋กœ ์ž‘๋™ํ•ฉ๋‹ˆ๋‹ค.

๊ฐ๋„๋ฅผ ์–ด๋–ป๊ฒŒ ๊ฐ์ง€ํ•ฉ๋‹ˆ๊นŒ?

๋‚˜๋Š” ๊ฐ ๋‹จ๊ณ„ (๊ฐ๊ฐ 1๋„)๋ฅผ ์‹œ๋„ํ•˜๊ณ  ์—ด์„ ๋”ฐ๋ผ ํ•ฉ๊ณ„ํ•˜๊ณ  ํ•ฉ๊ณ„ ๋ฒกํ„ฐ๋ฅผ ์–ป์Šต๋‹ˆ๋‹ค. ์‚ฌ๊ฐํ˜•์ด ๋˜‘๋ฐ”๋กœ์žˆ์„ ๋•Œ ์ด์ƒ์  ์œผ๋กœ์ด ํ•ฉ๊ณ„ ๋ฒกํ„ฐ์—์„œ ๋‘ ๊ฐ€์ง€ ๊ฐ‘์ž๊ธฐ ๋ณ€๊ฒฝ๋˜๋Š” ๊ฒƒ์ด ์ด์ƒ์ ์ž…๋‹ˆ๋‹ค. ์‚ฌ๊ฐํ˜•์ด ํŒ ์œ„์— ์žˆ์œผ๋ฉด ๋ณ€๊ฒฝ์ด ๋งค์šฐ ์ ์ง„์ ์ž…๋‹ˆ๋‹ค. ๊ทธ๋ž˜์„œ ๋‚˜๋Š” ์ฒซ ๋ฒˆ์งธ ๋ฏธ๋ถ„์„ ์‚ฌ์šฉํ•˜๊ณ  โ€˜์ ํ”„โ€™์˜ ์ˆ˜๋ฅผ ์ตœ์†Œํ™”ํ•˜๋ ค๊ณ ํ•ฉ๋‹ˆ๋‹ค. ์—ฌ๊ธฐ์„œ ์šฐ๋ฆฌ๊ฐ€ ์ตœ์†Œํ™”ํ•˜๋ ค๋Š” ๊ธฐ์ค€์˜ ๋„ํ‘œ๋ฅผ ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋„ค ๊ฐ€์ง€ ๊ฐ€๋Šฅํ•œ ์ˆ˜์ง ๋ฐฉํ–ฅ์— ํ•ด๋‹นํ•˜๋Š” ๋„ค ๊ฐ€์ง€ ์ตœ์†Œ๊ฐ’์„ ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ถ”๊ฐ€ ์ƒ๊ฐ : ์ฒ ์ €ํ•œ ๊ฐ๋„ ๊ฒ€์ƒ‰์— ๋งŽ์€ ๋ฌธ์ž๊ฐ€ ํ•„์š”ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์–ผ๋งˆ๋‚˜ ๋งŽ์€ ๊ณจํ”„๋ฅผ ์น  ์ˆ˜ ์žˆ๋Š”์ง€ ํ™•์‹คํ•˜์ง€ ์•Š์œผ๋ฉฐ ๋‚ด์žฅ ๋œ ์ตœ์ ํ™” ๋ฐฉ๋ฒ•์„ ์‚ฌ์šฉํ•˜๋ฉด ๋‹ฌ์„ฑ ํ•  ์ˆ˜ ์žˆ์„์ง€ ์˜์‹ฌ๋ฉ๋‹ˆ๋‹ค. ์šฐ๋ฆฌ๊ฐ€ ์ฐพ๊ณ  ์žˆ์ง€ ์•Š์€ ๋‹น์‹ ์€ ์‰ฝ๊ฒŒ ๊ฐ๋„ ์ž‘์€ ์Šคํ… ํฌ๊ธฐ๋ฅผ ์„ ํƒํ•˜์—ฌ (ํฐ ์‚ฌ์ง„์˜) ์ •ํ™•๋„๋ฅผ ๊ฐœ์„ ํ•˜๊ณ  ๋Œ€์ฒด ํ•  ์ˆ˜ ์žˆ๋„๋ก์—๋งŒ 360 ยฐ ๋Œ€์‹ ์— 90 ยฐ๋ฅผ ๊ฒ€์ƒ‰ ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค 0:360์™€ 0:.1:90๊ทธ๋Ÿฐ somehting ๋‚˜. ๊ทธ๋Ÿฌ๋‚˜ ์–ด์จŒ๋“  ๋„์ „์€ ๊ณจํ”„๋ณด๋‹ค๋Š” ๊ฐ•๋ ฅํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ฐพ๋Š” ๊ฒƒ์ด ๋” ์–ด๋ ค์› ์œผ๋ฉฐ ๊ณจํ”„ ์–ธ์–ด์˜ ํ•ญ๋ชฉ์ด ๋‚ด ์ œ์ถœ์„ ํ›จ์”ฌ ๋’ค์— ๋‚จ๊ฒจ ๋†“์„ ๊ฒƒ์ด๋ผ๊ณ  ํ™•์‹ ํ•ฉ๋‹ˆ๋‹ค. =)

์ถ”์‹  : ๋ˆ„๊ตฐ๊ฐ€ Matlab / Octave์—์„œ ๊ณจํ”„ ์–ธ์–ด๋ฅผ ํŒŒ์ƒ์‹œ์ผœ์•ผํ•ฉ๋‹ˆ๋‹ค.

์ถœ๋ ฅ

์˜ˆ 1 :

 25    39

์˜ˆ 2 :

 25    24

์•”ํ˜ธ

๊ณจํ”„ :

s=input('');r=sum(s=='n');S=reshape(s',nnz(s)/r,r)';S=S(:,1:2:end-2)=='.';m=Inf;a=0;for d=0:360;v=sum(1-~diff(sum(imrotate(S,d))));if v<m;m=v;a=d;end;end;S=imrotate(S,a);x=sum(S);y=sum(S');disp([sum(x>mean(x)),sum(y>mean(y))])

์–ธ ๊ณจํ”„ ๋“œ :

s=input('');
r=sum(s=='n');
S=reshape(s',nnz(s)/r,r)';
S=S(:,1:2:end-2)=='.';
m=Inf;a=0;
for d=0:360;
    v=sum(1-~diff(sum(imrotate(S,d))));
    if v<m;
        m=v;a=d;
    end;
end;
S=imrotate(S,a);
x=sum(S);y=sum(S');
disp([sum(x>mean(x)),sum(y>mean(y))])

๋‹ต๋ณ€

CJam, 68 65 64 ๋ฐ”์ดํŠธ

์ด๊ฒƒ์€ ์กฐ๊ธˆ ๋” ๊ณจํ”„๋ฅผ ์น  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค ..

qN/2f%{{:QN*'.#Qz,)mdQ2$>2<".X"f#_~>@@0=?Qz}2*;@@-@@-mhSQWf%}2*;

์ž‘๋™ ์›๋ฆฌ

๋‹น์‹ ์ด ๊ทธ๊ฒƒ์— ๋Œ€ํ•ด ์ƒ๊ฐํ•˜๋ฉด ๋…ผ๋ฆฌ๋Š” ๋งค์šฐ ๊ฐ„๋‹จํ•ฉ๋‹ˆ๋‹ค.

์ž…๋ ฅ X.์กฐํ•ฉ ์—์„œ ํ•„์š”ํ•œ ๊ฒƒ์€ ๋‘ ๊ฐœ์˜ ์ธ์ ‘ํ•œ ๋ณ€์˜ 3 ์ขŒํ‘œ์ž…๋‹ˆ๋‹ค. ์šฐ๋ฆฌ๊ฐ€ ๊ทธ๋“ค์„ ์–ป๋Š” ๋ฐฉ๋ฒ•์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

First

์‚ฌ๊ฐํ˜•์˜ ๋ชจ๋“  ๋ฐฉํ–ฅ .์—์„œ ์ž…๋ ฅ ์ „์ฒด์˜ ์ฒซ ๋ฒˆ์งธ ๋Š” ๋ชจ์„œ๋ฆฌ ์ค‘ ํ•˜๋‚˜๊ฐ€๋ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ..

XXXXXXXXXXXXXX
XXXXXXX...XXXX
XXXX.......XXX
X............X
XX.........XXX
XXXX...XXXXXXX
XXXXXXXXXXXXXX

์—ฌ๊ธฐ์„œ ์ฒซ ๋ฒˆ์งธ .๋Š” ๋‘ ๋ฒˆ์งธ ์ค„, 8 ๋ฒˆ์งธ ์—ด์— ์žˆ์Šต๋‹ˆ๋‹ค.

๊ทธ๋Ÿฌ๋‚˜ ๊ทธ๊ฒƒ์€ ์•„๋‹™๋‹ˆ๋‹ค. ์šฐ๋ฆฌ๋Š” .์กฐ์ •์„ํ•˜๊ณ  ์˜ค๋ฅธ์ชฝ ๋์˜ ์ขŒํ‘œ๋ฅผ ์–ป๊ธฐ ์œ„ํ•ด ํ•ด๋‹น ๋ผ์ธ ์˜ ๋Ÿฐ ๋„ˆ๋น„๋ฅผ ์ขŒํ‘œ์— ์ถ”๊ฐ€ํ•ด์•ผํ•ฉ๋‹ˆ๋‹ค.

Second

์œ„์˜ ์‚ฌ๊ฐํ˜•์„ ๋ฐ”๊พธ๋ฉด (๊ฐœํ–‰์œผ๋กœ ํ”ผ๋ฒ—) ์™ผ์ชฝ ์•„๋ž˜ ๋ชจ์„œ๋ฆฌ๊ฐ€ ์œ„ ๋‹จ๊ณ„๋ฅผ ๋Œ€์‹ ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ ์—ฌ๊ธฐ์„œ ์šฐ๋ฆฌ๋Š” .์–ด์จŒ๋“  ๊ฐ€์žฅ์ž๋ฆฌ์˜ ์™ผ์ชฝ ์•„๋ž˜ ์ขŒํ‘œ๋ฅผ ์–ป๊ณ  ์‹ถ์„ ๋•Œ ์‹คํ–‰ ๊ธธ์ด๋ฅผ ๋ณด์ƒํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค (์กฐ์˜ฎ๊น€ ํ˜•ํƒœ๋Š” ์—ฌ์ „ํžˆ ์ฒ˜์Œ์œผ๋กœ ๋ฐœ์ƒํ•ฉ๋‹ˆ๋‹ค .)

Rest two

๋‘ ์ขŒํ‘œ๋ฅผ ์‰ฌ๋ ค๋ฉด ์ง์‚ฌ๊ฐํ˜•์„ ๊ฐ€๋กœ๋กœ ๋’ค์ง‘์–ด ์œ„์˜ ๋‘ ๋‹จ๊ณ„๋ฅผ ์ˆ˜ํ–‰ํ•˜์‹ญ์‹œ์˜ค. ์—ฌ๊ธฐ ๋ชจํ‰์ด ์ค‘ ํ•˜๋‚˜๋Š” ์ฒ˜์Œ ๋‘ ๊ฐœ์—์„œ ๊ณตํ†ต์ž…๋‹ˆ๋‹ค.

4๋ฅผ ๋ชจ๋‘ ์–ป์€ ํ›„์—๋Š” ๊ฐ„๋‹จํ•œ ์ˆ˜ํ•™์„ ์ˆ˜ํ–‰ํ•˜์—ฌ ๊ฑฐ๋ฆฌ๋ฅผ ์–ป์Šต๋‹ˆ๋‹ค.

์ด์ œ ์ด๊ฒƒ์€ ๊ฐ€์žฅ ์ •ํ™•ํ•œ ๋ฐฉ๋ฒ•์€ ์•„๋‹ˆ์ง€๋งŒ ์˜ค๋ฅ˜ ์—ฌ๋ฐฑ ๋‚ด์—์„œ์™€ ์‚ฌ๊ฐํ˜•์˜ ๊ฐ€๋Šฅํ•œ ๋ชจ๋“  ๋ฐฉํ–ฅ์—์„œ ์ž˜ ์ž‘๋™ํ•ฉ๋‹ˆ๋‹ค.

์ฝ”๋“œ ํ™•์žฅ (๋น„ํŠธ ๊ตฌ์‹)

qN/2f%{{:QN*'.#Q0=,)md}:A~1$Q='.e=+QzA@@-@@-mhSQWf%}2*;
qN/2f%                               e# Read the input, split on newlines and squish it
      {   ...   }2*                  e# Run the code block two times, one for each side
{:QN*'.#Q0=,)md}:A~                  e# Store the code block in variable A and execute it
 :QN*                                e# Store the rows in Q variable and join by newlines
     '.#                             e# Get the location of the first '.'
        Q0=,)                        e# Get length + 1 of the first row
             md                      e# Take in X and Y and leave out X/Y and X%Y on stack
1$Q=                                 e# Get the row in which the first '.' appeared
    '.e=+                            e# Get number of '.' in that row and add it to X%Y
         QzA                         e# Transpose the rows and apply function A to get
                                     e# the second coordinate
            @@-@@-                   e# Subtract resp. x and y coordinates of the two corners
                  mh                 e# Calculate (diff_x**2 + diff_y**2)**0.5 to get 1 side
                    SQWF%            e# Put a space on stack and put the horizontally flipped
                                     e# version of the rows/rectangle all ready for next two
                                     e# coordinates and thus, the second side

์—ฌ๊ธฐ์—์„œ ์˜จ๋ผ์ธ์œผ๋กœ ์‚ฌ์šฉํ•ด๋ณด์‹ญ์‹œ์˜ค


๋‹ต๋ณ€

ํŒŒ์ด์ฌ 3, 347 337 ๋ฐ”์ดํŠธ

์ด๊ฒƒ์€ ๋‚ด๊ฐ€ ์˜ˆ์ƒํ–ˆ๋˜ ๊ฒƒ๋ณด๋‹ค ๋” ํž˜๋“ค์—ˆ์Šต๋‹ˆ๋‹ค. ์ง„ํ–‰์ค‘์ธ ์ž‘์—…โ€ฆ

def f(s):
 l=s.split('\n');r=range;v=sorted;w=len(l[0]);h=len(l);p=[[x,y]for x in r(w)for y in r(h)if'X'>l[y][x]];x,y=[sum(k)/w/h for k in zip(*p)];g=[[x/2,y]];d=lambda a:((a[0]/2-a[2]/2)**2+(a[1]-a[3])**2)**.5
 for i in r(3):g+=v(p,key=lambda c:~-(c in g)*sum(d(j+c)for j in g))[:1]
 print(v(map(d,[g[1]+g[2],g[2]+g[3],g[1]+g[3]]))[:2])

f๋ฌธ์ž์—ด์„ ์ธ์ˆ˜๋กœ ์‚ฌ์šฉํ•˜๊ณ  ๊ฒฐ๊ณผ๋ฅผ STDOUT์— ์ธ์‡„ ํ•˜๋Š” ํ•จ์ˆ˜ ๋ฅผ ์ •์˜ํ•ฉ๋‹ˆ๋‹ค .

Pyth, 87 84 82 81 75 72 71 ๋ฐ”์ดํŠธ

(์•„๋งˆ๋„ ์ง‘์— ๋„์ฐฉํ–ˆ์„ ๋•Œ, ๋ถ€์ •ํ™•ํ•˜๊ณ  ์กฐ์‚ฌ ์ค‘)

Km%2d.zJf<@@KeThTG*UhKUKPSm.adfqlT2ytu+G]ho*t}NGsm.a,kNGJ3]mccsklhKlKCJ

๋ฐฉ๋ฒ•์€ ์•„์ง ๋„ˆ๋ฌด ์˜ค๋ž˜. ๊ธฐ๋ณธ์ ์œผ๋กœ ์ด์ „ ํฌํŠธ์ž…๋‹ˆ๋‹ค. Pyth์˜ .a์œ ํด๋ฆฌ๋“œ ๊ฑฐ๋ฆฌ๋ฅผ ์‚ฌ๋ž‘ํ•ฉ๋‹ˆ๋‹ค . STDIN์„ ํ†ตํ•ด ์ž…๋ ฅ์„ ๊ฐ€์ ธ์˜ค๊ณ  STDOUT์„ ํ†ตํ•ด ์ถœ๋ ฅ์„ ์ œ๊ณตํ•ฉ๋‹ˆ๋‹ค. ์‚ฌ๊ฐํ˜•์ด ์•„๋‹Œ ๋ฌธ์ž๊ฐ€ ์†Œ๋ฌธ์ž ์ผ ๊ฒƒ์œผ๋กœ ์˜ˆ์ƒ๋ฉ๋‹ˆ๋‹ค x(๋ฌผ๋ก  ASCII ๊ฐ’ 98 ์ด์ƒ์˜ ๋ชจ๋“  ๊ฒƒ).

์—ฐ์‚ฐ

๋‘˜ ๋‹ค ๋™์ผํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค. ๊ธฐ๋ณธ์ ์œผ๋กœ ์‚ฌ๊ฐํ˜• ์˜์—ญ์˜ ์งˆ๋Ÿ‰ ์ค‘์‹ฌ์„ ํฌํ•จํ•˜๋Š” ๋ฐฐ์—ด๋กœ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋Ÿฐ ๋‹ค์Œ ์‚ฌ๊ฐํ˜•์˜ ๋ชจ๋“  ์ ์˜ ๋ฐฐ์—ด์— 3 ๊ฐœ์˜ ์ ์„ ์ถ”๊ฐ€ํ•˜๊ณ  ํ•ญ์ƒ ๋ฐฐ์—ด์—์žˆ๋Š” ์ ๊นŒ์ง€์˜ ์ตœ๋Œ€ ๊ฑฐ๋ฆฌ ๋ฅผ ๊ฐ€์ง„ ์ ์„ ์„ ํƒํ•ฉ๋‹ˆ๋‹ค . ๊ฒฐ๊ณผ๋Š” ํ•ญ์ƒ ์‚ฌ๊ฐํ˜•์˜ ๋‹ค๋ฅธ ๊ตฌ์„์— ์„ธ ์ ์ž…๋‹ˆ๋‹ค. ๊ทธ๋Ÿฐ ๋‹ค์Œ ์„ธ ์  ์‚ฌ์ด์˜ ์„ธ ๊ฑฐ๋ฆฌ๋ฅผ ๋ชจ๋‘ ๊ณ„์‚ฐํ•˜๊ณ  ๊ฐ€์žฅ ์งง์€ ๋‘ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ€์ ธ์˜ต๋‹ˆ๋‹ค.


๋‹ต๋ณ€

ํŒŒ์ด์ฌ 2, 342 ๋ฐ”์ดํŠธ

import sys
r=[]
h=.0
for l in sys.stdin:w=len(l);r+=[[x*.5,h]for x in range(0,w,2)if l[x:x+2]=='..'];h+=1
x,y=.0,.0
for p in r:x+=p[0];y+=p[1]
n=len(r)
x/=n
y/=n
m=.0
for p in r:
 p[0]-=x;p[1]-=y;d=p[0]**2+p[1]**2
 if d>m:m=d;u,v=p
m=.0
for p in r:
 d=p[0]*v-p[1]*u
 if d>m:m=d;s,t=p
print ((u-s)**2+(v-t)**2)**.5+1,((u+s)**2+(v+t)**2)**.5+1

์ด๊ฒƒ์€ @ Pietu1998์˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜์—์„œ ์˜๊ฐ์„ ์–ป์—ˆ์Šต๋‹ˆ๋‹ค. ํ•˜๋‚˜์˜ ๋ชจํ‰์ด๋ฅผ ์ค‘์‹ฌ์—์„œ ๊ฐ€์žฅ ๋จผ ์ง€์ ์œผ๋กœ ๊ฒฐ์ •ํ•˜๋Š” ์•„์ด๋””์–ด๊ฐ€ ํ•„์š”ํ•˜์ง€๋งŒ ๊ฑฐ๊ธฐ์—์„œ ๋‹ค๋ฆ…๋‹ˆ๋‹ค.

  • ๋‘ ๋ฒˆ์งธ ๋ชจ์„œ๋ฆฌ๋ฅผ ์ค‘์‹ฌ์—์„œ ์ฒซ ๋ฒˆ์งธ ๋ชจ์„œ๋ฆฌ๊นŒ์ง€ ๋ฒกํ„ฐ๊ฐ€์žˆ๋Š” ๊ฐ€์žฅ ํฐ ๊ต์ฐจ ๊ณฑ์ด์žˆ๋Š” ์ ์œผ๋กœ ๊ฒฐ์ •ํ•ฉ๋‹ˆ๋‹ค. ์ด๊ฒƒ์€ ์ค‘์‹ฌ์—์„œ ์ฒซ ๋ฒˆ์งธ ๋ชจ์„œ๋ฆฌ๊นŒ์ง€์˜ ์„ ์—์„œ ๊ฐ€์žฅ ํฐ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ€์ง„ ์ ์„ ์ œ๊ณตํ•ฉ๋‹ˆ๋‹ค.
  • ์„ธ ๋ฒˆ์งธ ๋ชจ์„œ๋ฆฌ๋Š” ์ค‘์•™์„ ๊ธฐ์ค€์œผ๋กœ ๋‘ ๋ฒˆ์งธ ๋ชจ์„œ๋ฆฌ์˜ ๋ฏธ๋Ÿฌ ์ด๋ฏธ์ง€์ด๋ฏ€๋กœ ๊ฒ€์ƒ‰ ํ•  ํ•„์š”๊ฐ€ ์—†์Šต๋‹ˆ๋‹ค.

๋”ฐ๋ผ์„œ ์ฝ”๋“œ๋Š” ๋‹ค์Œ ์ˆœ์„œ๋ฅผ ๋”ฐ๋ฆ…๋‹ˆ๋‹ค.

  • ์ฒซ ๋ฒˆ์งธ ๋ฃจํ”„๋Š” ์ž…๋ ฅ์˜ ์„  ์œ„์— ์žˆ์œผ๋ฉฐ r์‚ฌ๊ฐํ˜• ์  ๋ชฉ๋ก ์„ ์ž‘์„ฑํ•ฉ๋‹ˆ๋‹ค .
  • ๋‘ ๋ฒˆ์งธ ๋ฃจํ”„๋Š” ์‚ฌ๊ฐํ˜•์˜ ์ค‘์‹ฌ์„ ์ œ๊ณตํ•˜์—ฌ ๋ชจ๋“  ์‚ฌ๊ฐํ˜• ์ ์˜ ํ‰๊ท ์„ ๊ณ„์‚ฐํ•ฉ๋‹ˆ๋‹ค.
  • ์„ธ ๋ฒˆ์งธ ๋ฃจํ”„๋Š” ์ค‘์‹ฌ์—์„œ ๊ฐ€์žฅ ๋จผ ์ง€์ ์„ ์ฐพ์Šต๋‹ˆ๋‹ค. ์ด๊ฒƒ์ด ์ฒซ ๋ฒˆ์งธ ์ฝ”๋„ˆ์ž…๋‹ˆ๋‹ค. ๋™์‹œ์— ์  ์ขŒํ‘œ๊ฐ€ ๋‚˜๋จธ์ง€ ๊ณ„์‚ฐ์˜ ์ค‘์‹ฌ์„ ๊ธฐ์ค€์œผ๋กœ ๋ชฉ๋ก์˜ ์ ์—์„œ ์ค‘์‹ฌ์„ ๋บ๋‹ˆ๋‹ค.
  • ๋„ค ๋ฒˆ์งธ ๋ฃจํ”„๋Š” ๋ฒกํ„ฐ๊ฐ€ ์ฒซ ๋ฒˆ์งธ ๋ชจ์„œ๋ฆฌ์—์žˆ๋Š” ๊ฐ€์žฅ ํฐ ๊ต์ฐจ ๊ณฑ์ด์žˆ๋Š” ์ ์„ ์ฐพ์Šต๋‹ˆ๋‹ค. ์ด๊ฒƒ์€ ๋‘ ๋ฒˆ์งธ ์ฝ”๋„ˆ์ž…๋‹ˆ๋‹ค.
  • ์ฒซ ๋ฒˆ์งธ ๋ชจ์„œ๋ฆฌ์™€ ๋‘ ๋ฒˆ์งธ ๋ชจ์„œ๋ฆฌ ์‚ฌ์ด์˜ ๊ฑฐ๋ฆฌ์™€ ์ฒซ ๋ฒˆ์งธ ๋ชจ์„œ๋ฆฌ์™€ ๋‘ ๋ฒˆ์งธ ๋ชจ์„œ๋ฆฌ์˜ ๋ฏธ๋Ÿฌ ์ด๋ฏธ์ง€ ์‚ฌ์ด์˜ ๊ฑฐ๋ฆฌ๋ฅผ ์ธ์‡„ํ•ฉ๋‹ˆ๋‹ค.
  • 1.0์›๋ž˜ ๊ฑฐ๋ฆฌ ๊ณ„์‚ฐ์—๋Š” ํ”ฝ์…€ ์ธ๋ฑ์Šค๊ฐ€ ์‚ฌ์šฉ๋˜๋ฏ€๋กœ ๊ฑฐ๋ฆฌ์— ์ถ”๊ฐ€๋ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, 5 ๊ฐœ์˜ ํ”ฝ์…€์ด์žˆ๋Š” ๊ฒฝ์šฐ ๋งˆ์ง€๋ง‰ ํ”ฝ์…€๊ณผ ์ฒซ ๋ฒˆ์งธ ํ”ฝ์…€์˜ ์ธ๋ฑ์Šค ์ฐจ์ด๋Š” 4์— ๋ถˆ๊ณผํ•˜๋ฏ€๋กœ ์ตœ์ข… ๊ฒฐ๊ณผ์—์„œ ๋ณด์ƒ์ด ํ•„์š”ํ•ฉ๋‹ˆ๋‹ค.

์ •๋ฐ€๋„๋Š” ์•„์ฃผ ์ข‹์Šต๋‹ˆ๋‹ค. ๋‘ ๊ฐ€์ง€ ์˜ˆ๋ฅผ ๋“ค๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

$ cat rect1.txt | python Golf.py
24.5372045919 39.8329756779
$ cat rect2.txt | python Golf.py
23.803508502 24.5095563412

๋‹ต๋ณ€

ํŒŒ์ด์ฌ 2, 272 ๋ฐ”์ดํŠธ

์ด์ „ ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ์™„์ „ํžˆ ๋‹ค๋ฅธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ฏ€๋กœ ๋ณ„๋„์˜ ๋‹ต๋ณ€์œผ๋กœ ๊ฒŒ์‹œํ•˜์‹ญ์‹œ์˜ค.

import sys,math
y,a,r=0,0,0
l,t=[1<<99]*2
for s in sys.stdin:
 c=s.count('..')
 if c:a+=c;x=s.find('.')/2;l=min(l,x);r=max(r,x+c);t=min(t,y);b=y+1
 y+=1
r-=l
b-=t
p=.0
w,h=r,b
while w*h>a:c=math.cos(p);s=math.sin(p);d=c*c-s*s;w=(r*c-b*s)/d;h=(b*c-r*s)/d;p+=.001
print w,h

์ด ๋ฐฉ๋ฒ•์€ ๋ชจ์„œ๋ฆฌ๋ฅผ ์ „ํ˜€ ์‹๋ณ„ํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค. ๊ฒฝ๊ณ„ ์ƒ์ž์˜ ํฌ๊ธฐ (๋„ˆ๋น„์™€ ๋†’์ด)์™€ ํšŒ์ „ ๋œ ์‚ฌ๊ฐํ˜•์˜ ์˜์—ญ์ด ์‚ฌ๊ฐํ˜•์˜ ๋„ˆ๋น„์™€ ๋†’์ด๋ฅผ ๊ฒฐ์ •ํ•˜๊ธฐ์— ์ถฉ๋ถ„ํ•˜๋‹ค๋Š” ๊ด€์ฐฐ ๊ฒฐ๊ณผ๋ฅผ ๊ธฐ๋ฐ˜์œผ๋กœํ•ฉ๋‹ˆ๋‹ค.

์Šค์ผ€์น˜๋ฅผ ๋ณด๋ฉด ์‚ฌ๊ฐํ˜•์˜ ํฌ๊ธฐ / ํฌ๊ธฐ ๋ฐ ํšŒ์ „ ๊ฐ๋„ ๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ๊ฒฝ๊ณ„ ์ƒ์ž ์˜ ๋„ˆ๋น„ ( wb) ๋ฐ ๋†’์ด ( hb) ๋ฅผ ๊ณ„์‚ฐํ•˜๋Š” ๊ฒƒ์ด ๋งค์šฐ ์‰ฝ์Šต๋‹ˆ๋‹ค .whp

wb = w * cos(p) + h * sin(p)
hb = w * sin(p) + h * cos(p)

wb๋ฐ hb์ด๋ฏธ์ง€๋กœ๋ถ€ํ„ฐ ์ง์ ‘ ์ถ”์ถœ ๋  ์ˆ˜์žˆ๋‹ค. ํ”ฝ์…€ a์ˆ˜๋ฅผ ์„ธ์–ด ์‚ฌ๊ฐํ˜• ์˜ ์ „์ฒด ์˜์—ญ ์„ ๋น ๋ฅด๊ฒŒ ์ถ”์ถœ ํ•  ์ˆ˜๋„ ์žˆ์Šต๋‹ˆ๋‹ค ... ์šฐ๋ฆฌ๋Š” ์ง์‚ฌ๊ฐํ˜•์„ ๋‹ค๋ฃจ๊ธฐ ๋•Œ๋ฌธ์— ์ถ”๊ฐ€ ๋ฐฉ์ •์‹์„ ์–ป์Šต๋‹ˆ๋‹ค.

a = w * h

๋”ฐ๋ผ์„œ ์šฐ๋ฆฌ๋Š” 3 ๊ฐœ์˜ ๋ฏธ์ง€์ˆ˜ ( w, h๋ฐ p)๋ฅผ ๊ฐ€์ง„ 3 ๊ฐœ์˜ ๋ฐฉ์ •์‹์„ ๊ฐ€์ง€ ๋Š”๋ฐ, ์ด๋Š” ๋ฏธ์ง€์ˆ˜๋ฅผ ๊ฒฐ์ •ํ•˜๊ธฐ์— ์ถฉ๋ถ„ํ•ฉ๋‹ˆ๋‹ค. ์œ ์ผํ•œ ๋ฌธ์ œ๋Š” ๋ฐฉ์ •์‹์— ์‚ผ๊ฐ ํ•จ์ˆ˜๊ฐ€ ํฌํ•จ๋˜์–ด ์žˆ๊ณ  ์ ์–ด๋„ ์ธ๋‚ด์™€ ์ˆ˜ํ•™ ๊ธฐ์ˆ ๋กœ ์‹œ์Šคํ…œ์„ ์‰ฝ๊ฒŒ ๋ถ„์„ ํ•  ์ˆ˜ ์—†๋‹ค๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

๋‚ด๊ฐ€ ๊ตฌํ˜„ ํ•œ ๊ฒƒ์€ ๊ฐ๋„์— ๋Œ€ํ•œ ๋ฌด์ฐจ๋ณ„ ๋Œ€์ž…์ด๋‹ค p. ์ผ๋‹จ p์ฒ˜์Œ ๋‘ ๋ฐฉ์ •์‹์€ ์ƒ๊ธฐ์—์„œ ํ•ด๊ฒฐ ๋  ์ˆ˜์žˆ๋Š” ๋‘ ๊ฐœ์˜ ์„ ํ˜• ๋ฐฉ์ •์‹์˜ ์‹œ์Šคํ…œ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค wํ•˜๊ณ  h:

w = (wb * cos(p) - hb * sin(p)) / (cos(p) * cos(p) - sin(p) * sin(p))
h = (hb * cos(p) - wb * sin(p)) / (cos(p) * cos(p) - sin(p) * sin(p))

์ด ๊ฐ’์œผ๋กœ w * h์ง์‚ฌ๊ฐํ˜•์˜ ์ธก์ • ๋œ ์˜์—ญ๊ณผ ๋น„๊ตํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค . ๋‘ ๊ฐ’์€ ์–ด๋А ์‹œ์ ์—์„œ ์ด์ƒ์ ์œผ๋กœ ๋™์ผํ•ฉ๋‹ˆ๋‹ค. ์ด๊ฒƒ์€ ๋ฌผ๋ก  ๋ถ€๋™ ์†Œ์ˆ˜์  ์ˆ˜ํ•™์—์„œ๋Š” ์ผ์–ด๋‚˜์ง€ ์•Š์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค.

w * h๊ฐ๋„๊ฐ€ ์ฆ๊ฐ€ํ•จ์— ๋”ฐ๋ผ ๊ฐ’์ด ๊ฐ์†Œํ•ฉ๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ 0.0์—์„œ ์‹œ์ž‘ํ•œ ๋‹ค์Œ ์ฒ˜์Œ์œผ๋กœ w * h์ธก์ • ๋œ ์˜์—ญ๋ณด๋‹ค ์ž‘์„ ๋•Œ๊นŒ์ง€ ์ž‘์€ ๋‹จ๊ณ„ ์”ฉ ๊ฐ๋„๋ฅผ ์ฆ๊ฐ€์‹œํ‚ต๋‹ˆ๋‹ค .

์ฝ”๋“œ์—๋Š” ๋‘ ๊ฐ€์ง€ ์ฃผ์š” ๋‹จ๊ณ„ ๋งŒ ์žˆ์Šต๋‹ˆ๋‹ค.

  1. ์ž…๋ ฅ์—์„œ ๊ฒฝ๊ณ„ ์ƒ์ž ๋ฐ ์‚ฌ๊ฐํ˜• ์˜์—ญ์˜ ํฌ๊ธฐ๋ฅผ ์ถ”์ถœํ•˜์‹ญ์‹œ์˜ค.
  2. ์ข…๋ฃŒ ๊ธฐ์ค€์— ๋„๋‹ฌ ํ•  ๋•Œ๊นŒ์ง€ ํ›„๋ณด ๊ฐ๋„๋ฅผ ๋ฐ˜๋ณตํ•ฉ๋‹ˆ๋‹ค.

๋„ˆ๋น„์™€ ๋†’์ด๊ฐ€ ํฌ๊ฒŒ ๋‹ค๋ฅธ ์‚ฌ๊ฐํ˜•์˜ ๊ฒฝ์šฐ ์ถœ๋ ฅ ์ •๋ฐ€๋„๊ฐ€ ์ข‹์Šต๋‹ˆ๋‹ค. ๊ฑฐ์˜ ์ •์‚ฌ๊ฐํ˜•์ด๊ณ  45๋„ ๊ฐ€๊นŒ์ด ํšŒ์ „ ํ•œ ์‚ฌ๊ฐํ˜•์—์„œ๋Š” ๋‹ค์†Œ ๋ฌธ์ œ๊ฐ€ ์ƒ๊ฒจ ํ…Œ์ŠคํŠธ ์˜ˆ์ œ 2์˜ 7 % ์˜ค๋ฅ˜ ์žฅ์• ๋ฌผ์„ ๊ฑฐ์˜ ์ œ๊ฑฐ ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์˜ˆ์ œ 2์˜ ๋น„ํŠธ ๋งต์€ ์‹ค์ œ๋กœ ์•ฝ๊ฐ„ ์ด์ƒํ•˜๊ฒŒ ๋ณด์ž…๋‹ˆ๋‹ค. ์™ผ์ชฝ ๊ตฌ์„์ด ์˜์‹ฌ์Šค๋Ÿฝ๊ฒŒ ๋‘”ํ•ด ๋ณด์ž…๋‹ˆ๋‹ค. ์™ผ์ชฝ ๊ตฌ์„์— ํ•˜๋‚˜ ์ด์ƒ์˜ ํ”ฝ์…€์„ ์ถ”๊ฐ€ํ•˜๋ฉด ๋‘˜ ๋‹ค ๋‚˜์•„ ๋ณด์ด๋ฉฐ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ •๋ฐ€๋„๊ฐ€ ํ›จ์”ฌ ํ–ฅ์ƒ๋ฉ๋‹ˆ๋‹ค.


๋‹ต๋ณ€