In de voetsporen Ik publiceer problemen uit de Algorithm-track (klassieke sportprogrammering. In anderhalf uur moet je drie problemen oplossen in Java, C#, C++ of Python.)
1. Taart voor zes
Formulering van het probleem
De tijdslimiet bedraagt 4 seconden.
Je hebt een taart. Van bovenaf gezien heeft de taart de vorm van een (strikt) convexe veelhoek. U krijgt de coördinaten van de hoekpunten in gehele getallen X en Y.
Je hebt vijf vrienden. Je wilt de taart in zes stukken van gelijke oppervlakte verdelen (maar niet noodzakelijkerwijs dezelfde vorm). Natuurlijk kan iedereen het in vijf delen doen, maar alleen een professional kan het in drie delen doen.
Zoek drie sneden in rechte lijnen door één punt, waardoor de taart in zes gelijke delen wordt verdeeld. Print {x, y, d1, d2, d3}, waarbij (x, y) het gemeenschappelijke punt is van alle drie de sneden, en d1, d2, d3 de richtingshoeken van de sneden in radialen zijn.
DefinitieKlasse: CakeForSix
Methode: knippen
Parameters: int[], int[] Resultaat: double[] Methodehandtekening: double[] cut(int[] x, int[] y)
(zorg ervoor dat uw methode openbaar is)
Opmerkingen
- De positieve richting langs de x-as is 0 (radialen), de positieve richting langs de y-as is pi/2 (radialen).
- Een snede in de d-richting is vergelijkbaar met een snede in de pi*k+d-richting voor elk geheel getal k.
- U kunt elke richting uitvoeren, deze hoeft niet vanaf [0, pi) te komen.
- De grader berekent de oppervlakte van uw zes stukken taart dubbel. Het antwoord wordt geaccepteerd als het relatieve of absolute verschil tussen beide kleiner is dan 10^(-4).
- Om precies te zijn: laat X en Y de kleinste en grootste van uw zes gebieden zijn, berekend door de grader. Dan wordt uw antwoord geaccepteerd als Y
- (De originele versie van het probleem gebruikte een precisie van 1e-7 in plaats van 1e-4. Om dit probleem in het archief op te lossen, werd de precisielimiet verlaagd vanwege de aanwezigheid van aanroepgevallen die het probleem waarschijnlijk onoplosbaar zouden maken met een nauwkeurigheid van 1e-7. In een ideale wereld laten de limieten dergelijke gevallen niet toe en vereisen ze nog steeds hoge precisie, dus het oplossen van het probleem met enige algemene numerieke optimalisatie is niet eenvoudig.)
Beperkingen
- x bevat 3 tot en met 50 elementen.
- y bevat hetzelfde aantal elementen als x.
- alle coördinaten tussen 0 en 10 inclusief
- x en y definiëren een convexe veelhoek tegen de klok in.
origineel in het engels
Probleemstelling
Tijdslimiet is 4 seconden.
Je hebt een taart. Van bovenaf gezien is de taart een (strikt) convexe veelhoek. Je krijgt de coördinaten van de hoekpunten in int[]sx en y.
Je hebt vijf vrienden. Je wilt de cake nu in zes stukken van gelijke oppervlakte snijden (maar niet noodzakelijkerwijs van gelijke vorm). Natuurlijk kan iedereen dat in vijf keer doen, maar alleen een echte professional kan het in drie keer doen!
Zoek drie rechte lijnsneden die door hetzelfde punt gaan waar de cake in zes even grote delen is gesneden. Retourneer {x, y, d1, d2, d3}, waarbij (x, y) het gemeenschappelijke punt van de drie sneden is, en d1, d2, d3 hun richtingen in radialen zijn.
Definitie
Klasse: CakeForSix
Methode: knippen
Parameters: int[], int[] Resultaat: double[] Methodehandtekening: double[] cut(int[] x, int[] y)
(zorg ervoor dat uw methode openbaar is)
Opmerkingen
— De positieve richting langs de x-as is 0 (radialen), de positieve richting langs de y-as is pi/2 (radialen).
— Een snede in richting d is hetzelfde als een snede in richting pi*k+d voor elk geheel getal k.
— U kunt elke routebeschrijving retourneren, deze hoeft niet vanuit [0,pi) te zijn.
— De beoordelaar berekent de oppervlakte van uw zes taartstukken dubbel. Het antwoord wordt geaccepteerd als het relatieve of absolute verschil tussen beide kleiner is dan 10^(-4).
— Om precies te zijn: laat X en Y de kleinste en de grootste van uw zes gebieden zijn, zoals berekend door de beoordelaar. Dan wordt je antwoord geaccepteerd als Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (De originele versie van het probleem gebruikte 1e-7 precisie in plaats van 1e-4. Voor het oplossen van dit probleem in het archief werd de precisielimiet verlaagd vanwege het bestaan van uitdagingsgevallen die de taak hoogstwaarschijnlijk onoplosbaar maken met 1e-7 precisie In een ideale wereld zouden de beperkingen dergelijke gevallen niet toestaan en nog steeds een hoge nauwkeurigheid vereisen, zodat het niet eenvoudig is om het probleem op te lossen via een of andere algemene numerieke optimalisatie.)
beperkingen
— x zal tussen de 3 en 50 elementen bevatten.
— y zal hetzelfde aantal elementen hebben als x.
— Alle coördinaten liggen tussen 0 en 10,000, inclusief.
— x en y beschrijven een convexe veelhoek tegen de klok in.
Примеры
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Returns:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Een symmetrische maar onregelmatige zeshoek. Het voorbeeldantwoord komt overeen met het horizontaal doormidden snijden en twee andere sneden in het midden maken, waardoor elk stuk in drie stukken wordt verdeeld.
1)
{0, 1000, 0}
{0, 0, 1000}
Returns:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Rechte driehoek. Nogmaals, we kunnen beginnen met een van de drie sneden langs de symmetrieas.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Returns:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Onregelmatige vijfhoek.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Retourneert: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Een vierkant draaide 45 graden.
[]
Alleen geregistreerde gebruikers kunnen deelnemen aan het onderzoek. , Alsjeblieft.
Ik heb het probleem voor opgelost
-
in minder dan 10 minuten
-
10-30 minuten
-
30-60 minuten
-
1-2 uur
-
binnen ruim 2 uur
-
ander
42 gebruikers hebben gestemd. 47 gebruikers onthielden zich van stemming.
Bron: www.habr.com