ืืื ืื ืคืืกืกืืขืคึผืก ืืื ืึทืจืืืกืืขืื ืคึผืจืึธืืืขืืก ืคืื ืื ืึทืืืขืจืืืึทื ืฉืคึผืืจ (ืงืืืกืืฉืข ืกืคึผืึธืจื ืคึผืจืึธืืจืึทืืืื ื. ืืื ืืืื ืืื ืึท ืืึทืื ืฉืขื ืืืจ ืืึทืจืคึฟื ืฆื ืกืึธืืืืข ืืจืื ืคึผืจืึธืืืขืืก ืืื ืืืฉืึทืืืึท, C#, C++ ืึธืืขืจ ืคึผืืืืึธื.)
1. ืคึผืืจืึธื ืคึฟืึทืจ ืืขืงืก
ืืืกืืึธืืื ื ืคืื ืื ืคึผืจืึธืืืขื
ืื ืฆืืื ืืืืื ืืื 4 ืกืขืงืื ืืขืก.
ืืืจ ืืึธื ืึท ืคึผืืจืึธื. ืืืขื ืืืจ ืงืืง ืคืื ืืืืื, ืื ืฉืืืงื ืืื ืื ืคืึธืจืขื ืคืื ืึท (ืฉืืจืขื ื) ืงืึทื ืืืขืงืก ืคืืืขืง. ืืืจ ืืขื ืขื ืืขืืขืื ืื ืงืึธืืึธืจืืึทื ืึทืฅ ืคืื ืื ืืืขืจืืืกืขืก ืืื X ืืื Y ืื ืืึทืืืฉืขืจื.
ืืืจ ืืึธืื ืคืื ืฃ ืคืจืืื ื. ืืืจ ืืืืื ืฆื ืืืืื ืื ืคึผืืจืึธื ืืื ืืขืงืก ืืจืขืงืืขื ืคืื ืืืืึทื ืืขืื ื (ืึธืืขืจ ื ืื ืืึทืืืงืข ืื ืืขืืืข ืคืึธืจืขื). ืคืื ืงืืจืก, ืืืขืจ ืขืก ืื ืงืขื ืขื ืืึธื ืขืก ืืื ืคืื ืฃ ืงืึทืฅ, ืึธืืขืจ ืืืืื ืึท ืคึผืจืึธ ืงืขื ืขื ืืึธื ืขืก ืืื ืืจืืึท ืงืึทืฅ.
ืืขืคึฟืื ืขื ืืจืืึท ืงืึทืฅ ืืื ืืืืึทื ืฉืืจืืช ืืืจื ืืืื ืคืื ื ืืืึธืก ืืืขื ืืืืื ืื ืคึผืืจืึธื ืืื ืืขืงืก ืืืืึทื ืืืืื. ืืจืืง {x, y, d1, d2, d3}, ืืื (ืจืขื ืืืขื , ื) ืืื ืืขืจ ืคึผืจืึธืกื ืคืื ื ืคืื ืึทืืข ืืจืืึท ืงืึทืฅ, ืืื ื1, ื2, ื3 ืืขื ืขื ืื ืจืืืืื ื ืึทื ืืืขืก ืคืื ืื ืงืึทืฅ ืืื ืจืึทืืืึทื ื.
ืืขืคืื ืืฆืืขืงืืึทืก: CakeForSix
ืืืคึฟื: ืฉื ืืึทืื
ืคึผืึทืจืึทืืขืืขืจืก: int[], int[] ืจืขืืืจื ืก: ืืึธืคึผื[] ืืขืืึทื ืืกืืืข: ืืึธืคึผื[] cut(int[] x, int[] y)
(ืืืื ืืืืขืจ ืืืื ืืืคึฟื ืืื ืขืคื ืืืขื)
ืืขืจืืช
- ืื positive ืจืืืืื ื ืฆืืืืืขื ืื X-ืึทืงืก ืืื 0 (ืจืึทืืืึทื ื), ืื positive ืจืืืืื ื ืฆืืืืืขื ืื ื-ืึทืงืก ืืื ืคึผื/2 (ืจืึทืืืึทื ื).
- ื ืืืจืืฉื ืื ืืื ืื ืจืืืืื ื ืืื ืขื ืืขื ืฆื ืึท ืฉื ืืึทืื ืืื ืื ืคึผื*ืง+ื ืจืืืืื ื ืคึฟืึทืจ ืงืืื ืืึทื ืฅ ื ืืืขืจ ืง.
- ืืืจ ืงืขื ืขื ืึทืจืืืกืคืืจื ืงืืื ืืื ืกืืจืืงืฆืืขืก, ืืื ืืึธื ื ืื ืืึธืื ืฆื ืืืื ืคึฟืื [0, ืคึผื).
- ืื ืืจืืืืขืจ ืืืขื ืจืขืืขื ืขื ืื ืฉืื ืคืื ืืืื ืืขืงืก ืืจืขืงืืขื ืคืื ืฉืืืงื ืืื ืืึทืืึทืื. ืืขืจ ืขื ืืคืขืจ ืืืขื ืืืื ืื ืืขื ืืืขื ืืืื ืื ืจืขืืึทืืืื ืึธืืขืจ ืึทืืกืึธืืื ืืืืืง ืฆืืืืฉื ืืื ืืื ืืืืื ืืงืขืจ ืืื 10^(-4).
- ืืขืจ ืืขื ืื, ืืึธืื X ืืื Y ืืืื ืื ืงืืขื ืกืืขืจ ืืื ืืจืขืกืืขืจ ืคืื ืืืื ืืขืงืก ืืขืืืื ืงืึทืืงืืึทืืืืืื ืืืจื ืื ืืจืืืืขืจ. ืืขืจื ืึธื ืืืื ืขื ืืคืขืจ ืืืขื ืืืื ืื ืืขื ืืืขื ืืืื ื
- (ืืขืจ ืึธืจืืืื ืขื ืืืขืจืกืืข ืคืื โโืืขื ืคึผืจืึธืืืขื ืืขื ืืฆื ืึท ืคึผืื ืืืขืืงืืึทื ืคืื 1e-7 ืึทื ืฉืืึธื ืคืื 1e-4. ืฆื ืกืึธืืืืข ืืขื ืคึผืจืึธืืืขื ืืื ืื ืึทืจืงืืืื, ืื ืคึผืื ืืืขืืงืืึทื ืืืืื ืืื ืืึธืืขืจื ืจืขืื ืฆื ืืขื ืืืึทืืืึทื ืคืื ืคืึทื ืงืึทืกืขืก ืืืึธืก ืืืึธืื ืืกืชึผืื ืืึทืื ืื ืคึผืจืึธืืืขื ืึทื ืกืึทืืืืึทืืึทื ืืื ืึท ืคึผืื ืืืขืืงืืึทื ืคืื 1e-7. ืืื ืึทื ืืืืขืื ืืืขืื, ืื ืืืืึทืฅ ืืึธื ื ืื ืืึธืื ืึทืืึท ืงืึทืกืขืก ืืื ื ืึธื ืืึทืจืคื ืืืื ืคึผืื ืืืขืืงืืึทื, ืึทืืื ืกืึทืืืืื ื ืื ืคึผืจืึธืืืขื ืืื ืขืืืขืืข ืืขื ืขืจืึทื ื ืืืขืจืืงืึทื ืึทืคึผืืึทืืึทืืืืฉืึทื ืืื ื ืืฉื ืืจืื ื.)
ืจืืกืืจืืงืฉืึทื ื
- x ืึผืืื 3-50 ืขืืขืืขื ืื ืื ืงืืืกืืื.
- y ืึผืืื ืื ืืขืืืข ื ืืืขืจ ืคืื ืขืืขืืขื ืื ืืื x.
- ืึทืืข ืงืึธืืึธืจืืึทื ืึทืฅ ืฆืืืืฉื 0 ืืื 10 ืื ืงืืืกืืื
- x ืืื y ืืขืคืื ืืจื ืึท ืงืึทื ืืืขืงืก ืคืืืขืง ืืื ืึท ืงืึทืื ืืขืจืงืืึธืงืืืืื ืจืืืืื ื.
ืึธืจืืืื ืขื ืืื ืขื ืืืืฉ
ืคึผืจืึธืืืขื ืกืืึทืืขืืขื ื
ืฆืืื ืฉืืขืืจ ืืื 4 ืกืขืงืื ืืขืก.
ืืืจ ืืึธืื ืึท ืฉืืืงื. ืืขืืขื ืคืื ืืืืื, ืื ืฉืืืงื ืืื ืึท (ืฉืืจืขื ื) ืงืึทื ืืืขืงืก ืคืืืขืง. ืืืจ ืืึทืงืืืขื ืื ืงืึธืืึธืจืืึทื ืึทืฅ ืคืื ืืืึทื ืืืขืจืืืกืขืก ืืื ืื ืื ื[]sx ืืื y.
ืืืจ ืืึธืื ืคืื ืฃ ืคืจืืื ื. ืืืจ ืืืฆื ืืืืื ืฆื ืฉื ืืึทืื ืื ืฉืืืงื ืืื ืืขืงืก ืืจืขืงืืขื ืคืื ืืืืึทื ืืขืื ื (ืึธืืขืจ ื ืื ืืึทืืืงืข ืืืืึทื ืคืึธืจืขื). ืคืื ืงืืจืก, ืืืขืจ ืขืก ืื ืงืขื ืขื ืืึธื ืืึธืก ืืื ืคืื ืฃ ืงืึทืฅ - ืึธืืขืจ ืืืืื ืึท ืืืช ืคึผืจืึธ ืงืขื ืขื ืืึธื ืืึธืก ืืื ืืจืื!
ืืขืคึฟืื ืขื ืืจืืึท ืืืืึทื-ืฉืืจื ืงืึทืฅ ืืืื ืคืืจืืื ืืืจื ืื ืืขืืืข ืคืื ื ืืืึธืก ืฉื ืืึทืื ืื ืฉืืืงื ืืื ืืขืงืก ืืืืึทื ืืจืืืก ืืืืื. ืฆืืจืืงืงืืืขื {x, y, d1, d2, d3}, ืืื (x, y) ืืื ืืขืจ ืคึผืจืึธืกื ืคืื ื ืคืื ืื ืืจืื ืฉื ืืึทืื, ืืื ื1, ื2, ื3 ืืขื ืขื ืืืืขืจ ืืื ืกืืจืืงืฆืืขืก ืืื ืจืึทืืืึทื ื.
ืืขืคืื ืืฆืืข
ืงืืึทืก: CakeForSix
ืืืคึฟื: ืฉื ืืึทืื
ืคึผืึทืจืึทืืขืืขืจืก: int[], int[] ืจืขืืืจื ืก: ืืึธืคึผื[] ืืขืืึทื ืืกืืืข: ืืึธืคึผื[] cut(int[] x, int[] y)
(ืืืื ืืืืขืจ ืืืื ืืืคึฟื ืืื ืขืคื ืืืขื)
ื ืึธืืขืก
โ ืื ืคืืืืืืืืข ืจืืืืื ื ืฆืืืืืขื ืื X ืึทืงืก ืืื 0 (ืจืึทืืืึทื ื), ืื positive ืจืืืืื ื ืฆืืืืืขื ืื ื ืึทืงืก ืืื ืคึผื/2 (ืจืึทืืืึทื ื).
โ ื ืืืจืืฉื ืื ืืื ืจืืืืื ื ื ืืื ืื ืืขืืืข ืืื ื ืืืจืืฉื ืื ืืื ืจืืืืื ื ืคื*ืง+ื ืคืืจ ืืขืื ืืื ืฆื ืฆืื ืง.
- ืืืจ ืงืขื ื ืฆืืจืืงืงืืืขื ืงืืื ืืื ืกืืจืืงืฆืืขืก, ืืื ืืึธื ื ืื ืืึธืื ืฆื ืืืื ืคึฟืื [0,ืคึผื).
- ืืขืจ ืืจืืืืขืจ ืืืขื ืจืขืืขื ืขื ืื ืืขืืืื ืคืื ืืืื ืืขืงืก ืฉืืืงื ืืจืขืงืืขื ืืื ืืึทืืึทืื. ืืขืจ ืขื ืืคืขืจ ืืืขื ืืืื ืื ืืขื ืืืขื ืืืื ืื ืจืขืืึทืืืื ืึธืืขืจ ืึทืืกืึธืืื ืืืืืง ืฆืืืืฉื ืืื ืืื ืืืืื ืืงืขืจ ืืื 10^(-4).
- ืืขืจ ืืขื ืื, ืืึธืื X ืืื Y ืืืื ืื ืงืืขื ืกืืขืจ ืืื ืื ืืจืขืกืืข ืคืื โโืืืื ืืขืงืก ืืขืืืื, ืืื ืงืึทืืคึผืืืืึทื ืืืจื ืื ืืจืืืืขืจ. ืืขืจื ืึธื, ืืืื ืขื ืืคืขืจ ืืืขื ืืืื ืื ืืขื ืืืขื ืืืื ื < ืืึทืงืก( X + 10 ^ (-4), X * (1 + 10 ^ (-4))).
โ (ืืขืจ ืึธืจืืืื ืขื ืืืขืจืกืืข ืคืื โโืืขื ืคึผืจืึธืืืขื ืืขื ืืฆื 1e-7 ืคึผืื ืืืขืืงืืึทื ืึทื ืฉืืึธื ืคืื 1e-4. ืคึฟืึทืจ ืกืึทืืืืื ื ืืขื ืคึผืจืึธืืืขื ืืื ืื ืึทืจืงืืืื, ืื ืคึผืื ืืืขืืงืืื ืืืืื ืืื ืืึธืืขืจื ืจืขืื ืฆื ืืขืจ ืขืงืืืกืืขื ืฅ ืคืื ืึทืจืืืกืจืืคื ืงืึทืกืขืก ืืืึธืก ืจืืึฟ ืืกืชึผืื ืืึทืื ืื ืึทืจืืขื ืึทื ืกืึทืืืืึทืืึทื ืืื 1e-7 ืคึผืื ืืืขืืงืืึทื ืืื ืึทื ืืืืขืื ืืืขืื, ืื ืงืึทื ืกืืจืืื ืฅ ืืืึธืื ื ืืฉื ืืึธืื ืึทืืึท ืงืึทืกืขืก ืืื ื ืึธื ืืึทืจืคื ืืืื ืคึผืื ืืืขืืงืืึทื, ืึทืืื ืึทื ืขืก ืืื ื ืืฉื ืืจืื ื ืฆื ืกืึธืืืืข ืื ืคึผืจืึธืืืขื ืืืจื ืขืืืขืืข ืืขื ืขืจืึทื ื ืืืขืจืืง ืึทืคึผืืึทืืึทืืืืฉืึทื.)
ืงืึทื ืกืืจืืื ืฅ
- x ืืืขื ืืึธืื ืฆืืืืฉื 3 ืืื 50 ืขืืขืืขื ืื, ืื ืงืืืกืืื.
โ y ืืืขื ืืึธืื ืื ืืขืืืข ื ืืืขืจ ืคืื ืขืืขืืขื ืื ืืื x.
- ืึทืืข ืงืึธืืึธืจืืึทื ืึทืฅ ืืืขื ืืืื ืฆืืืืฉื 0 ืืื 10,000, ืื ืงืืืกืืื.
- x ืืื y ืืืขื ืืึทืฉืจืืึทืื ืึท ืงืึทื ืืืขืงืก ืคืืืขืง ืืื ืงืึทืื ืืขืจืงืืึธืงืืืืื ืกืืจ.
ืขืงืกืึทืืคึผืืขืก
0)
{0}
{10}
ืงืขืจื:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787}
ื ืกืึทืืขืืจืืงืึทื ืึธืืขืจ ืืจืขืืืึทืืขืจ ืืขืงืกืึทืืึธื. ืืขืจ ืืืืฉืคึผืื ืขื ืืคืขืจ ืงืึธืจืึทืกืคึผืึทื ืื ืฆื ืงืึทืืื ื ืขืก ืืื ืืึทืื ืืึธืจืืืึทื ืืึทืื ืืื ืืึทืื ืฆืืืื ืื ืืขืจืข ืงืึทืฅ ืึทืจืึธืคึผ ืื ืฆืขื ืืขืจ ืืืึธืก ืืืืื ืืขืืขืจ ืฉืืืง ืืื ืืจืืึท ืืืืื.
1)
{0}
{0}
ืงืขืจื:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753}
ืจืขืื ืืจืืึทืขืง. ืืืืืขืจ, ืืืจ ืงืขื ืขื ืึธื ืืืืื ืืื ืืืื ืขืจ ืคืื ืืจืืึท ืงืึทืฅ ืฆืืืืืขื ืื ืึทืงืก ืคืื ืกืืืขืืจืืข.
2)
{40}
{30}
ืงืขืจื:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475}
ืืจืขืืืึทืืขืจ ืคึผืขื ืืึทืืึธื.
3)
{300}
{500}
ืจืขืืืจื ืก: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705}
ื ืงืืืึทืืจืึทื ืจืึธืืืืืืื 45 ืืืืจืื.
[]
ืืืืื ืจืขืืืกืืจืืจื ื ืืฆืขืจืก ืงืขื ืขื ืึธื ืืืื ื ืขืืขื ืืื ืื ืืืขืจืืืืง. ืืืืข.
ืืื ืกืึทืืืื ืื ืคึผืจืึธืืืขื ืคึฟืึทืจ
-
ืืื ืืืืื ืืงืขืจ ืืื 10 ืืื ืื
-
ืงืกื ืืืงืก-ืงืกื ืืืงืก ืืื ืื
-
ืงืกื ืืืงืก-ืงืกื ืืืงืก ืืื ืื
-
1-2 ืฉืขื
-
ืืื ืืขืจ ืืื 2 ืฉืขื
-
ืึทื ืืขืจืขืจ
42 ืืื ืืฆืขืจ ืืืื ืืขืฉืืืื. 47 ืืื ืืฆืขืจ ืืืื ืืื ืืคืืขืืืืื.
ืืงืืจ: www.habr.com