Ramona Dragoș at 13:58, 6 January 2024

2024-01-06T13:58:03Z

← Older revision		Revision as of 13:58, 6 January 2024
Line 1:		Line 1:
	== Enunt ==		== Enunt ==
	Gigel îşi imaginează lumea în varianta 2d, adică reprezentată în sistem de coordonate cartezian XOY. Fiecare persoană din grupul celor N prieteni ai săi este reprezentată în plan printr-un punct identificat prin abscisa şi ordonata sa. În lumea sa 2d, plouă ca în Anglia, iar picăturile de ploaie pică paralel cu axa OY, de la o înălţime infinită. Ca să îi ferească pe prietenii săi de ploaie, îşi propune să le construiască apărători pe care le va reprezenta pe hartă prin segmente de dreaptă.		Gigel îşi imaginează lumea în varianta '''2d''', adică reprezentată în sistem de coordonate cartezian '''XOY'''. Fiecare persoană din grupul celor '''N''' prieteni ai săi este reprezentată în plan printr-un punct identificat prin abscisa şi ordonata sa. În lumea sa '''2d''', plouă ca în Anglia, iar picăturile de ploaie pică paralel cu axa '''OY''', de la o înălţime infinită. Ca să îi ferească pe prietenii săi de ploaie, îşi propune să le construiască apărători pe care le va reprezenta pe hartă prin segmente de dreaptă.
	== Cerința ==		== Cerința ==
	Ştiind că nu poate să deseneze pe hartă decât segmente de lungimi egale, determinaţi care este lungimea minimă a unui segment astfel încât trasând cel mult K segmente, toți cei N prieteni ai săi să fie protejați de ploaie.		Ştiind că nu poate să deseneze pe hartă decât segmente de lungimi egale, determinaţi care este lungimea minimă a unui segment astfel încât trasând cel mult '''K''' segmente, toți cei '''N''' prieteni ai săi să fie protejați de ploaie.
	== Date de intrare ==		== Date de intrare ==
	Fişierul de intrare 2din.txt conţine:		Fişierul de intrare '''2din.txt''' conţine:
	*pe prima linie numerele naturale N şi K;		*pe prima linie numerele naturale '''N''' şi '''K''';
	*pe următoarele N linii se află perechi de numere reale x y, cu exact trei zecimale fiecare, reprezentând abscisa şi ordonata punctului corespunzător fiecărui prieten al lui Gigel;		*pe următoarele '''N''' linii se află perechi de numere reale '''x y''', cu exact trei zecimale fiecare, reprezentând abscisa şi ordonata punctului corespunzător fiecărui prieten al lui Gigel;
	== Date de ieșire ==		== Date de ieșire ==
	Fişierul de ieşire 2dout.txt va conţine pe prima linie un singur număr real, cu trei zecimale reprezentând lungimea minimă a unui segment din cele trasate de Gigel.		Fişierul de ieşire '''2dout.txt''' va conţine pe prima linie un singur număr real, cu trei zecimale reprezentând lungimea minimă a unui segment din cele trasate de Gigel.
	== Restricții și precizări ==		== Restricții și precizări ==
	*1 &les; K < N &les; 200000		*'''1 &les; K < N &les; 200000'''
	*-1000000.000 &les; x,y &les; 1000000.000		*'''-1000000.000 &les; x,y &les; 1000000.000'''
	*Lungimea minimă a unui segment pe care îl va trasa Gigel este 1.000		*Lungimea minimă a unui segment pe care îl va trasa Gigel este '''1.000'''
	*Rezultatul va fi afişat cu o eroare de cel mult 0.001		*Rezultatul va fi afişat cu o eroare de cel mult '''0.001'''
	*Un segment trasat între punctele (x1, y1) şi (x2, y2) protejează toate punctele de pe segment şi din semiplanul “de sub” dreapta ce trece prin aceste puncte şi care au abscisele în intervalul închis [x1, x2].		*Un segment trasat între punctele '''(x1, y1)''' şi '''(x2, y2)''' protejează toate punctele de pe segment şi din semiplanul “de sub” dreapta ce trece prin aceste puncte şi care au abscisele în intervalul închis '''[x1, x2]'''.
	== Exemplu 1 ==		== Exemplu 1 ==
	;2din.txt		;'''2din.txt'''
	:5 3		:5 3
	:-5.000 1.000		:-5.000 1.000
Line 23:		Line 23:
	:3.000 -2.000		:3.000 -2.000
	:1.000 2.000		:1.000 2.000
	;2d.out		;'''2d.out'''
	:1.~~500~~		:2.000
	<br>		<br>
	== Exemplu 2 ==		== Exemplu 2 ==
	;2din.txt		;'''2din.txt'''
	:0 0		:0 0
	:0 0		:0 0
	:0 0		:0 0
	;2dout.txt		;'''2dout.txt'''
	:~~0.000~~		:Nu au fost respectate cerintele impuse
	<br>		<br>
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	#0705 - 2D		#0705 - 2D
	~~import sys~~
	import math		import math

	def ~~min_segment_length~~(points, K):		def is_covered(points, length, K):
	points.sort() ~~# Sortăm punctele după coordonata pe axa OX~~		points.sort()

	~~left~~ = 0.0		last_point = points[0]
	~~right~~ = ~~sys.float_info.max~~		segments = 1

	~~while right~~ - ~~left~~ > ~~0.001~~:		for point in points:
	~~mid~~ = ~~(left + right) / 2.0~~		if point - last_point > length:
	~~covered~~ = 0		segments += 1
			last_point = point

	~~for i in range(1, len(points)):~~		return segments <= K
	~~distance~~ = ~~points[i][0] - points[i - 1][0]~~
	~~covered += max(0, math.ceil((distance - mid) / mid))~~

	if ~~covered <=~~ K:		def find_min_segment_length(N, K, points):
			left, right = 0, max(points)

			while abs(left - right) > 0.001:
			mid = (left + right) / 2

			if is_covered(points, mid, K):
	right = mid		right = mid
	else:		else:
	left = mid		left = mid

	return round(~~left~~, 3)		return round(right, 3)

			def check_restrictions(N, K, points):
			if not(1 <= K < N <= 200000):
			return False
			for point in points:
			if not (-1000000.000 <= point <= 1000000.000):
			return False
			return True

	def main():		def main():
	with open("2din.txt", "r") as file_in:		with open("2din.txt", "r") as file_in, open("2dout.txt", "w") as file_out:
	N, K = map(int, file_in.readline().split())		N, K = map(int, file_in.readline().split())
	points = [~~tuple(map~~(~~float,~~ file_in.readline().split())) for _ in range(N)]		points = [float(file_in.readline().split()[0]) for _ in range(N)]

	~~result = min_segment_length~~(~~points~~, K)		if not check_restrictions(N, K, points):
			file_out.write("Nu au fost respectate cerintele impuse\n")
			return

	~~with open~~(~~"2dout.txt"~~, ~~"w"~~) ~~as file_out:~~		result = find_min_segment_length(N, K, points)
	file_out.write(f"{result:.3f}\n")		file_out.write(f"{result:.3f}\n")

Ramona Dragoș: Pagină nouă: == Enunt == Gigel îşi imaginează lumea în varianta 2d, adică reprezentată în sistem de coordonate cartezian XOY. Fiecare persoană din grupul celor N prieteni ai săi este reprezentată în plan printr-un punct identificat prin abscisa şi ordonata sa. În lumea sa 2d, plouă ca în Anglia, iar picăturile de ploaie pică paralel cu axa OY, de la o înălţime infinită. Ca să îi ferească pe prietenii săi de ploaie, îşi propune să le construiască apărători pe...

2023-12-21T13:18:51Z

Pagină nouă: == Enunt == Gigel îşi imaginează lumea în varianta 2d, adică reprezentată în sistem de coordonate cartezian XOY. Fiecare persoană din grupul celor N prieteni ai săi este reprezentată în plan printr-un punct identificat prin abscisa şi ordonata sa. În lumea sa 2d, plouă ca în Anglia, iar picăturile de ploaie pică paralel cu axa OY, de la o înălţime infinită. Ca să îi ferească pe prietenii săi de ploaie, îşi propune să le construiască apărători pe...

New page

== Enunt ==
Gigel îşi imaginează lumea în varianta 2d, adică reprezentată în sistem de coordonate cartezian XOY. Fiecare persoană din grupul celor N prieteni ai săi este reprezentată în plan printr-un punct identificat prin abscisa şi ordonata sa. În lumea sa 2d, plouă ca în Anglia, iar picăturile de ploaie pică paralel cu axa OY, de la o înălţime infinită. Ca să îi ferească pe prietenii săi de ploaie, îşi propune să le construiască apărători pe care le va reprezenta pe hartă prin segmente de dreaptă.
== Cerința ==
Ştiind că nu poate să deseneze pe hartă decât segmente de lungimi egale, determinaţi care este lungimea minimă a unui segment astfel încât trasând cel mult K segmente, toți cei N prieteni ai săi să fie protejați de ploaie.
== Date de intrare ==
Fişierul de intrare 2din.txt conţine:
*pe prima linie numerele naturale N şi K;
*pe următoarele N linii se află perechi de numere reale x y, cu exact trei zecimale fiecare, reprezentând abscisa şi ordonata punctului corespunzător fiecărui prieten al lui Gigel;
== Date de ieșire ==
Fişierul de ieşire 2dout.txt va conţine pe prima linie un singur număr real, cu trei zecimale reprezentând lungimea minimă a unui segment din cele trasate de Gigel.
== Restricții și precizări ==
*1 &les; K < N &les; 200000
*-1000000.000 &les; x,y &les; 1000000.000
*Lungimea minimă a unui segment pe care îl va trasa Gigel este 1.000
*Rezultatul va fi afişat cu o eroare de cel mult 0.001
*Un segment trasat între punctele (x1, y1) şi (x2, y2) protejează toate punctele de pe segment şi din semiplanul “de sub” dreapta ce trece prin aceste puncte şi care au abscisele în intervalul închis [x1, x2].
== Exemplu 1 ==
;2din.txt
:5 3
:-5.000 1.000
:-2.000 3.000
:3.000 2.000
:3.000 -2.000
:1.000 2.000
;2d.out
:1.500
<br>
== Exemplu 2 ==
;2din.txt
:0 0
:0 0
:0 0
;2dout.txt
:0.000
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#0705 - 2D
import sys
import math

def min_segment_length(points, K):
points.sort() # Sortăm punctele după coordonata pe axa OX

left = 0.0
right = sys.float_info.max

while right - left > 0.001:
mid = (left + right) / 2.0
covered = 0

for i in range(1, len(points)):
distance = points[i][0] - points[i - 1][0]
covered += max(0, math.ceil((distance - mid) / mid))

if covered <= K:
right = mid
else:
left = mid

return round(left, 3)

def main():
with open("2din.txt", "r") as file_in:
N, K = map(int, file_in.readline().split())
points = [tuple(map(float, file_in.readline().split())) for _ in range(N)]

result = min_segment_length(points, K)

with open("2dout.txt", "w") as file_out:
file_out.write(f"{result:.3f}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

0705 - 2D - Revision history

Ramona Dragoș at 13:58, 6 January 2024