TopCoder ਓਪਨ 2019 ਚੁਣੌਤੀ: ਪਾਈ ਨੂੰ ਛੇ ਟੁਕੜਿਆਂ ਵਿੱਚ ਕੱਟੋ

ਕਦਮਾਂ ਵਿੱਚ "ਸਾਡੀ ਟੀਮ ਜਿੱਤੀ: ਟੌਪਕੋਡਰ ਓਪਨ 2019" ਮੈਂ ਐਲਗੋਰਿਦਮ ਟਰੈਕ ਤੋਂ ਸਮੱਸਿਆਵਾਂ ਪ੍ਰਕਾਸ਼ਿਤ ਕਰ ਰਿਹਾ ਹਾਂ। (ਕਲਾਸਿਕ ਪ੍ਰਤੀਯੋਗੀ ਪ੍ਰੋਗਰਾਮਿੰਗ। ਤੁਹਾਨੂੰ ਡੇਢ ਘੰਟੇ ਵਿੱਚ ਜਾਵਾ, C#, C++, ਜਾਂ ਪਾਈਥਨ ਵਿੱਚ ਤਿੰਨ ਸਮੱਸਿਆਵਾਂ ਹੱਲ ਕਰਨੀਆਂ ਪੈਣਗੀਆਂ।)

1. ਛੇ ਲਈ ਪਾਈ

ਸਮੱਸਿਆ ਦਾ ਗਠਨ

ਸਮਾਂ ਸੀਮਾ: 4 ਸਕਿੰਟ।

ਤੁਹਾਡੇ ਕੋਲ ਇੱਕ ਪਾਈ ਹੈ। ਉੱਪਰੋਂ ਦੇਖਣ 'ਤੇ, ਪਾਈ ਇੱਕ (ਸਖਤ ਤੌਰ 'ਤੇ) ਕਨਵੈਕਸ ਬਹੁਭੁਜ ਦੀ ਸ਼ਕਲ ਵਿੱਚ ਹੈ। ਤੁਹਾਨੂੰ ਸਿਖਰਾਂ, X ਅਤੇ Y ਦੇ ਪੂਰਨ ਅੰਕ ਨਿਰਦੇਸ਼ਾਂਕ ਦਿੱਤੇ ਗਏ ਹਨ।

ਤੁਹਾਡੇ ਪੰਜ ਦੋਸਤ ਹਨ। ਤੁਸੀਂ ਇੱਕ ਪਾਈ ਨੂੰ ਛੇ ਬਰਾਬਰ ਆਕਾਰ ਦੇ ਟੁਕੜਿਆਂ ਵਿੱਚ ਵੰਡਣਾ ਚਾਹੁੰਦੇ ਹੋ (ਪਰ ਜ਼ਰੂਰੀ ਨਹੀਂ ਕਿ ਇੱਕੋ ਆਕਾਰ ਦਾ ਹੋਵੇ)। ਯਕੀਨਨ, ਕੋਈ ਵੀ ਇਸਨੂੰ ਪੰਜ ਕੱਟਾਂ ਵਿੱਚ ਕਰ ਸਕਦਾ ਹੈ, ਪਰ ਸਿਰਫ਼ ਇੱਕ ਪੇਸ਼ੇਵਰ ਹੀ ਇਸਨੂੰ ਤਿੰਨ ਵਿੱਚ ਕਰ ਸਕਦਾ ਹੈ।

ਇੱਕ ਸਾਂਝੇ ਬਿੰਦੂ ਰਾਹੀਂ ਸਿੱਧੀਆਂ ਰੇਖਾਵਾਂ ਵਾਲੇ ਤਿੰਨ ਕੱਟ ਲੱਭੋ ਜੋ ਪਾਈ ਨੂੰ ਛੇ ਬਰਾਬਰ-ਖੇਤਰ ਵਾਲੇ ਟੁਕੜਿਆਂ ਵਿੱਚ ਵੰਡਦੇ ਹਨ। {x, y, d1, d2, d3} ਪ੍ਰਿੰਟ ਕਰੋ, ਜਿੱਥੇ (x, y) ਤਿੰਨਾਂ ਕੱਟਾਂ ਦਾ ਸਾਂਝਾ ਬਿੰਦੂ ਹੈ, ਅਤੇ d1, d2, d3 ਰੇਡੀਅਨ ਵਿੱਚ ਕੱਟਾਂ ਦੇ ਕੋਣ ਹਨ।

ਪਰਿਭਾਸ਼ਾਕਲਾਸ: ਕੇਕਫੋਰਸਿਕਸ
ਢੰਗ: ਕੱਟਣਾ
ਪੈਰਾਮੀਟਰ: int[], int[]
ਵਾਪਸੀ: ਡਬਲ[]
ਢੰਗ ਦਸਤਖਤ: ਡਬਲ[] ਕੱਟ(ਇੰਟ[] ਐਕਸ, ਇੰਟਰ[] ਵਾਈ)
(ਯਕੀਨੀ ਬਣਾਓ ਕਿ ਤੁਹਾਡਾ ਤਰੀਕਾ ਜਨਤਕ ਹੈ)

ਨੋਟਸ

• x-ਧੁਰੇ ਦੇ ਨਾਲ-ਨਾਲ ਸਕਾਰਾਤਮਕ ਦਿਸ਼ਾ 0 (ਰੇਡੀਅਨ) ਹੈ, y-ਧੁਰੇ ਦੇ ਨਾਲ-ਨਾਲ ਸਕਾਰਾਤਮਕ ਦਿਸ਼ਾ pi/2 (ਰੇਡੀਅਨ) ਹੈ।
• d ਦਿਸ਼ਾ ਵਿੱਚ ਕੱਟ ਕਿਸੇ ਵੀ ਪੂਰਨ ਅੰਕ k ਲਈ pi*k+d ਦਿਸ਼ਾ ਵਿੱਚ ਕੱਟ ਦੇ ਸਮਾਨ ਹੈ।
• ਤੁਸੀਂ ਕੋਈ ਵੀ ਦਿਸ਼ਾ-ਨਿਰਦੇਸ਼ ਆਉਟਪੁੱਟ ਕਰ ਸਕਦੇ ਹੋ, ਉਹਨਾਂ ਨੂੰ [0, pi) ਤੋਂ ਹੋਣਾ ਜ਼ਰੂਰੀ ਨਹੀਂ ਹੈ।
• ਗ੍ਰੇਡਰ ਤੁਹਾਡੇ ਛੇ ਕੇਕ ਦੇ ਟੁਕੜਿਆਂ ਦੇ ਖੇਤਰਾਂ ਦੀ ਗਣਨਾ ਡਬਲਜ਼ ਵਿੱਚ ਕਰੇਗਾ। ਜੇਕਰ ਉਹਨਾਂ ਵਿਚਕਾਰ ਸਾਪੇਖਿਕ ਜਾਂ ਸੰਪੂਰਨ ਅੰਤਰ 10^(-4) ਤੋਂ ਘੱਟ ਹੈ ਤਾਂ ਉੱਤਰ ਸਵੀਕਾਰ ਕੀਤਾ ਜਾਵੇਗਾ।
• ਹੋਰ ਸਪਸ਼ਟ ਤੌਰ 'ਤੇ, ਗ੍ਰੇਡਰ ਦੁਆਰਾ ਗਿਣੇ ਗਏ ਤੁਹਾਡੇ ਛੇ ਖੇਤਰਾਂ ਵਿੱਚੋਂ X ਅਤੇ Y ਨੂੰ ਸਭ ਤੋਂ ਛੋਟਾ ਅਤੇ ਸਭ ਤੋਂ ਵੱਡਾ ਮੰਨ ਲਓ। ਫਿਰ ਤੁਹਾਡਾ ਜਵਾਬ ਸਵੀਕਾਰ ਕੀਤਾ ਜਾਵੇਗਾ ਜੇਕਰ Y
• (ਸਮੱਸਿਆ ਦੇ ਮੂਲ ਸੰਸਕਰਣ ਵਿੱਚ 1e-4 ਦੀ ਬਜਾਏ 1e-7 ਸ਼ੁੱਧਤਾ ਦੀ ਵਰਤੋਂ ਕੀਤੀ ਗਈ ਸੀ। ਇਸ ਮੁੱਦੇ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ, ਕਾਲ ਕੇਸਾਂ ਦੀ ਮੌਜੂਦਗੀ ਦੇ ਕਾਰਨ ਪੁਰਾਲੇਖ ਵਿੱਚ ਸ਼ੁੱਧਤਾ ਸੀਮਾ ਨੂੰ ਘਟਾ ਦਿੱਤਾ ਗਿਆ ਸੀ ਜੋ ਸੰਭਾਵਤ ਤੌਰ 'ਤੇ 1e-7 ਸ਼ੁੱਧਤਾ ਨਾਲ ਸਮੱਸਿਆ ਨੂੰ ਗੁੰਝਲਦਾਰ ਬਣਾਉਂਦੇ ਹਨ। ਇੱਕ ਆਦਰਸ਼ ਸੰਸਾਰ ਵਿੱਚ, ਪਾਬੰਦੀਆਂ ਅਜਿਹੇ ਮਾਮਲਿਆਂ ਨੂੰ ਰੋਕਦੀਆਂ ਹਨ ਅਤੇ ਫਿਰ ਵੀ ਉੱਚ ਸ਼ੁੱਧਤਾ ਦੀ ਲੋੜ ਹੁੰਦੀ ਹੈ, ਇਸ ਲਈ ਕੁਝ ਆਮ ਸੰਖਿਆਤਮਕ ਅਨੁਕੂਲਤਾ ਨਾਲ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨਾ ਸਿੱਧਾ ਨਹੀਂ ਹੈ।)

ਪ੍ਰਤਿਬੰਧ

• x ਵਿੱਚ 3 ਤੋਂ 50 ਤੱਤ ਸ਼ਾਮਲ ਹਨ।
• y ਵਿੱਚ x ਦੇ ਬਰਾਬਰ ਤੱਤ ਹਨ।
• 0 ਅਤੇ 10,000 ਦੇ ਵਿਚਕਾਰ ਸਾਰੇ ਨਿਰਦੇਸ਼ਾਂਕ ਸ਼ਾਮਲ ਹਨ
• x ਅਤੇ y ਇੱਕ ਕਨਵੈਕਸ ਬਹੁਭੁਜ ਨੂੰ ਘੜੀ ਦੀ ਉਲਟ ਦਿਸ਼ਾ ਵਿੱਚ ਪਰਿਭਾਸ਼ਿਤ ਕਰਦੇ ਹਨ।

ਮੂਲ ਅੰਗਰੇਜ਼ੀ ਵਿੱਚ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਸਮਾਂ ਸੀਮਾ 4 ਸਕਿੰਟ ਹੈ।

ਤੁਹਾਡੇ ਕੋਲ ਇੱਕ ਕੇਕ ਹੈ। ਉੱਪਰੋਂ ਦੇਖਿਆ ਜਾ ਰਿਹਾ ਹੈ, ਕੇਕ ਇੱਕ (ਸਖਤ ਤੌਰ 'ਤੇ) ਕਨਵੈਕਸ ਬਹੁਭੁਜ ਹੈ। ਤੁਹਾਨੂੰ int[]sx ਅਤੇ y ਵਿੱਚ ਇਸਦੇ ਸਿਖਰਾਂ ਦੇ ਨਿਰਦੇਸ਼ਾਂਕ ਦਿੱਤੇ ਗਏ ਹਨ।

ਤੁਹਾਡੇ ਪੰਜ ਦੋਸਤ ਹਨ। ਹੁਣ ਤੁਸੀਂ ਕੇਕ ਨੂੰ ਬਰਾਬਰ ਖੇਤਰਫਲ ਦੇ ਛੇ ਟੁਕੜਿਆਂ ਵਿੱਚ ਕੱਟਣਾ ਚਾਹੁੰਦੇ ਹੋ (ਪਰ ਜ਼ਰੂਰੀ ਨਹੀਂ ਕਿ ਇੱਕੋ ਆਕਾਰ ਦਾ ਹੋਵੇ)। ਬੇਸ਼ੱਕ, ਕੋਈ ਵੀ ਇਹ ਪੰਜ ਕੱਟਾਂ ਵਿੱਚ ਕਰ ਸਕਦਾ ਹੈ - ਪਰ ਸਿਰਫ਼ ਇੱਕ ਸੱਚਾ ਪੇਸ਼ੇਵਰ ਹੀ ਇਹ ਤਿੰਨ ਵਿੱਚ ਕਰ ਸਕਦਾ ਹੈ!

ਉਸੇ ਬਿੰਦੂ ਵਿੱਚੋਂ ਲੰਘਦੇ ਤਿੰਨ ਸਿੱਧੀਆਂ-ਰੇਖਾਵਾਂ ਵਾਲੇ ਕੱਟ ਲੱਭੋ ਜਿਸਨੇ ਕੇਕ ਨੂੰ ਛੇ ਬਰਾਬਰ ਵੱਡੇ ਹਿੱਸਿਆਂ ਵਿੱਚ ਕੱਟਿਆ ਹੈ। {x, y, d1, d2, d3} ਵਾਪਸ ਕਰੋ, ਜਿੱਥੇ (x, y) ਤਿੰਨ ਕੱਟਾਂ ਦਾ ਸਾਂਝਾ ਬਿੰਦੂ ਹੈ, ਅਤੇ d1, d2, d3 ਰੇਡੀਅਨ ਵਿੱਚ ਉਹਨਾਂ ਦੀਆਂ ਦਿਸ਼ਾਵਾਂ ਹਨ।

ਪਰਿਭਾਸ਼ਾ

ਕਲਾਸ: ਕੇਕਫੋਰਸਿਕਸ
ਢੰਗ: ਕੱਟਣਾ
ਪੈਰਾਮੀਟਰ: int[], int[]
ਵਾਪਸੀ: ਡਬਲ[]
ਢੰਗ ਦਸਤਖਤ: ਡਬਲ[] ਕੱਟ(ਇੰਟ[] ਐਕਸ, ਇੰਟਰ[] ਵਾਈ)
(ਯਕੀਨੀ ਬਣਾਓ ਕਿ ਤੁਹਾਡਾ ਤਰੀਕਾ ਜਨਤਕ ਹੈ)

ਸੂਚਨਾ
— x ਧੁਰੇ ਦੇ ਨਾਲ-ਨਾਲ ਸਕਾਰਾਤਮਕ ਦਿਸ਼ਾ 0 (ਰੇਡੀਅਨ) ਹੈ, y ਧੁਰੇ ਦੇ ਨਾਲ-ਨਾਲ ਸਕਾਰਾਤਮਕ ਦਿਸ਼ਾ pi/2 (ਰੇਡੀਅਨ) ਹੈ।
— ਕਿਸੇ ਵੀ ਪੂਰਨ ਅੰਕ k ਲਈ ਦਿਸ਼ਾ d ਵਿੱਚ ਕੱਟ pi*k+d ਦਿਸ਼ਾ ਵਿੱਚ ਕੱਟ ਦੇ ਸਮਾਨ ਹੈ।
— ਤੁਸੀਂ ਕੋਈ ਵੀ ਦਿਸ਼ਾ-ਨਿਰਦੇਸ਼ ਵਾਪਸ ਕਰ ਸਕਦੇ ਹੋ, ਇਹ ਜ਼ਰੂਰੀ ਨਹੀਂ ਕਿ ਉਹ [0,pi) ਤੋਂ ਹੋਣ।
— ਗ੍ਰੇਡਰ ਤੁਹਾਡੇ ਛੇ ਕੇਕ ਦੇ ਟੁਕੜਿਆਂ ਦੇ ਖੇਤਰਾਂ ਦੀ ਗਣਨਾ ਡਬਲਜ਼ ਵਿੱਚ ਕਰੇਗਾ। ਜੇਕਰ ਉਹਨਾਂ ਵਿਚਕਾਰ ਸਾਪੇਖਿਕ ਜਾਂ ਸੰਪੂਰਨ ਅੰਤਰ 10^(-4) ਤੋਂ ਘੱਟ ਹੈ ਤਾਂ ਉੱਤਰ ਸਵੀਕਾਰ ਕੀਤਾ ਜਾਵੇਗਾ।
— ਹੋਰ ਸਪਸ਼ਟ ਤੌਰ 'ਤੇ, X ਅਤੇ Y ਨੂੰ ਤੁਹਾਡੇ ਛੇ ਖੇਤਰਾਂ ਵਿੱਚੋਂ ਸਭ ਤੋਂ ਛੋਟਾ ਅਤੇ ਸਭ ਤੋਂ ਵੱਡਾ ਮੰਨੋ, ਜਿਵੇਂ ਕਿ ਗ੍ਰੇਡਰ ਦੁਆਰਾ ਗਿਣਿਆ ਗਿਆ ਹੈ। ਫਿਰ, ਤੁਹਾਡਾ ਜਵਾਬ ਸਵੀਕਾਰ ਕੀਤਾ ਜਾਵੇਗਾ ਜੇਕਰ Y <max( X + 10^(-4), X * (1+10^(-4)) )।
— (ਸਮੱਸਿਆ ਦੇ ਮੂਲ ਸੰਸਕਰਣ ਵਿੱਚ 1e-4 ਦੀ ਬਜਾਏ 1e-7 ਸ਼ੁੱਧਤਾ ਦੀ ਵਰਤੋਂ ਕੀਤੀ ਗਈ ਸੀ। ਪੁਰਾਲੇਖ ਵਿੱਚ ਇਸ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ ਸ਼ੁੱਧਤਾ ਸੀਮਾ ਨੂੰ ਚੁਣੌਤੀ ਦੇ ਮਾਮਲਿਆਂ ਦੀ ਮੌਜੂਦਗੀ ਦੇ ਕਾਰਨ ਘਟਾ ਦਿੱਤਾ ਗਿਆ ਸੀ ਜੋ ਸੰਭਾਵਤ ਤੌਰ 'ਤੇ 1e-7 ਸ਼ੁੱਧਤਾ ਨਾਲ ਕਾਰਜ ਨੂੰ ਅਸੰਭਵ ਬਣਾਉਂਦੇ ਹਨ। ਇੱਕ ਆਦਰਸ਼ ਸੰਸਾਰ ਵਿੱਚ ਪਾਬੰਦੀਆਂ ਅਜਿਹੇ ਮਾਮਲਿਆਂ ਦੀ ਆਗਿਆ ਨਹੀਂ ਦੇਣਗੀਆਂ ਅਤੇ ਫਿਰ ਵੀ ਉੱਚ ਸ਼ੁੱਧਤਾ ਦੀ ਲੋੜ ਹੁੰਦੀ ਹੈ, ਇਸ ਲਈ ਕੁਝ ਆਮ ਸੰਖਿਆਤਮਕ ਅਨੁਕੂਲਤਾ ਦੁਆਰਾ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨਾ ਆਸਾਨ ਨਹੀਂ ਹੈ।)

ਰੁਕਾਵਟਾਂ
— x ਵਿੱਚ 3 ਤੋਂ 50 ਤੱਤ ਹੋਣਗੇ, ਜਿਨ੍ਹਾਂ ਵਿੱਚ ਇਹ ਸ਼ਾਮਲ ਹੋਣਗੇ।
— y ਵਿੱਚ x ਦੇ ਬਰਾਬਰ ਤੱਤ ਹੋਣਗੇ।
— ਸਾਰੇ ਕੋਆਰਡੀਨੇਟ 0 ਅਤੇ 10,000 ਦੇ ਵਿਚਕਾਰ ਹੋਣਗੇ, ਸਮੇਤ।
— x ਅਤੇ y ਇੱਕ ਕਨਵੈਕਸ ਬਹੁਭੁਜ ਨੂੰ ਘੜੀ ਦੇ ਉਲਟ ਕ੍ਰਮ ਵਿੱਚ ਦਰਸਾਉਣਗੇ।

ਮਿਸਾਲ

0)

{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
ਵਾਪਸੀ:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }

ਇੱਕ ਸਮਰੂਪ, ਪਰ ਅਨਿਯਮਿਤ, ਛੇਭੁਜ। ਉਦਾਹਰਣ ਦਾ ਉੱਤਰ ਇਸਨੂੰ ਖਿਤਿਜੀ ਤੌਰ 'ਤੇ ਅੱਧੇ ਵਿੱਚ ਕੱਟਣ ਅਤੇ ਕੇਂਦਰ ਵਿੱਚ ਦੋ ਹੋਰ ਕੱਟ ਬਣਾਉਣ, ਹਰੇਕ ਅੱਧੇ ਨੂੰ ਤਿੰਨ ਵਿੱਚ ਵੰਡਣ ਦੇ ਸਮਾਨ ਹੈ।

1)

{0, 1000, 0
{0, 0, 1000
ਵਾਪਸੀ:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }

ਸੱਜਾ ਤਿਕੋਣ। ਦੁਬਾਰਾ ਫਿਰ, ਅਸੀਂ ਸਮਰੂਪਤਾ ਦੇ ਧੁਰੇ ਦੇ ਨਾਲ ਤਿੰਨ ਕੱਟਾਂ ਵਿੱਚੋਂ ਇੱਕ ਨਾਲ ਸ਼ੁਰੂ ਕਰ ਸਕਦੇ ਹਾਂ।

2)

{40, 70, 90, 90, 50
{30, 20, 40, 100, 60
ਵਾਪਸੀ:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }

ਅਨਿਯਮਿਤ ਪੰਜਭੁਜ।

3)

{300, 400, 300, 200}
{500, 600, 700, 600}
ਵਾਪਸੀ: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }

ਇੱਕ ਵਰਗ 45 ਡਿਗਰੀ ਘੁੰਮਿਆ ਹੋਇਆ ਸੀ।

[ਸਰੋਤ]

ਸਿਰਫ਼ ਰਜਿਸਟਰਡ ਉਪਭੋਗਤਾ ਹੀ ਸਰਵੇਖਣ ਵਿੱਚ ਹਿੱਸਾ ਲੈ ਸਕਦੇ ਹਨ। ਸਾਈਨ - ਇਨ, ਤੁਹਾਡਾ ਸੁਆਗਤ ਹੈ.

ਮੈਂ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕੀਤਾ ਹੈ

• 10 ਮਿੰਟ ਤੋਂ ਵੀ ਘੱਟ ਸਮੇਂ ਵਿੱਚ

• 10-30 ਮਿੰਟ

• 30-60 ਮਿੰਟ

• 1-2 ਘੰਟੇ

• 2 ਘੰਟਿਆਂ ਤੋਂ ਵੱਧ

• ਹੋਰ

42 ਉਪਭੋਗਤਾਵਾਂ ਨੇ ਵੋਟ ਕੀਤਾ। 47 ਉਪਭੋਗਤਾ ਬਚੇ ਰਹੇ।

ਸਰੋਤ: www.habr.com