포럼

COCI00625

Berilij

레이팅 미적용

난이도

시간 제한

512MB

메모리 제한

맞았습니다!!

제출 수

0.0%

정답률

레이팅

의견: 0

설명

Little sheep Be (short for Berilij) was kidnapped by the aliens, and they have a
rather unusual request for her. They want to hire her.
Precisely on Saturday, November $5^{th}$ , the aliens plan to visit Earth with $$n$$ spaceships
and reward the best COCI contestants (and maybe hire them too). Their spaceships
are perfect circles.
Due to safety reasons, they chose $$m$$ pairs of spaceships that have to touch exter-
nally when they land. They have already determined the landing coordinates
of the center point for each of the spaceships, and Be’s task is to determine the radius of each of the
spaceships, so the conditions are satisfied.
$$In$$ the image, the left and the right pairs $$of$$ spaceships $$do$$ not satisfy the condition $$of$$ touching externally.
The pair $$of$$ spaceships $$in$$ the middle fulfills the condition $$of$$ touching externally.
Spaceships are very expensive, and their cost is equal to their area, so the aliens are asking Be to determine
the radii with the minimum cost of the spaceships.
Their advanced technology allows spaceships to overlap, and, even more interestingly, they know how to
make a spaceship with radius equal to 0.
If there is no set of radii that satisfies the conditions, aliens expect Be to inform them about it. If Be
doesn’t succeed in determining the radii, they will hire her as lunch.

제약

Subtask 1 (15 points): $$n$$ is odd, and each of the spaceships should touch exactly two other spaceships.

Subtask 2 (25 points): There exists at least one way to determine the radii so the conditions are satisfied.

Subtask 3 (30 points): For each pair of spaceships (a, b), there’s at most one sequence of distinct spaceships that starts in $$a$$ , and finishes in $$b$$ , and all adjacent spaceships in the sequence are necessarily touching.

Subtask 4 (40 points): No additional constraints. Your answer will be considered correct if, for each radius of the $$n$$ spaceships, its absolute or relative error doesn’t exceed $10^{−}$ ^{4}. In other words, if your answer for the $$i-th$$ spaceship is $$r@@RISE_MATH_BLOCK_0@@ci$$ , then your answer wil be considered correct if | $$r@@RISE_MATH_BLOCK_1@@ci$$ | ≤ $10^{−}$ ^{4} or | ^{r}^{−}}^{ci} $$r$$ $$ci$$ | ≤ $10^{−}$ ^{4

입력 형식

The first line contains two integers $$n$$ and $$m$$ ( $1 \le n$ , $m \le 10^{5}$ ), the number of spaceships, and the number
of conditions.
The following $$n$$ lines contain real numbers $$x@@RISE_MATH_BLOCK_0@@i$$ (− $10\,000 \le x@@RISE_MATH_BLOCK_1@@i$ and $$b@@RISE_MATH_BLOCK_2@@i$$ , b $i \le n$ , a $$i$$ ̸ = $$b@@RISE_MATH_BLOCK_3@@i-th$$ and $$b@@RISE_MATH_BLOCK_4@@i$$ , b $$i$$ )
there will be at most one such condition.

출력 형식

If there is no solution, in the first and only line print NE. Otherwise, in the first line print DA, and in the
$$i-th$$ of the following $$n$$ lines print the radius of the $$i-th$$ spaceship.

서브태스크

서브태스크	점수	설명
1	15점	$$n$$ is odd, and each of the spaceships should touch exactly two other spaceships.
2	25점	There exists at least one way to determine the radii so the conditions are satisfied.
3	30점	For each pair of spaceships (a, b), there’s at most one sequence of distinct spaceships that starts in $$a$$ , and finishes in $$b$$ , and all adjacent spaceships in the sequence are necessarily touching.
4	40점	No additional constraints. Your answer will be considered correct if, for each radius of the $$n$$ spaceships, its absolute or relative error doesn’t exceed $10^{−}$ ^{4}. In other words, if your answer for the $$i-th$$ spaceship is $$r@@RISE_MATH_BLOCK_0@@ci$$ , then your answer wil be considered correct if \| $$r@@RISE_MATH_BLOCK_1@@ci$$ \| ≤ $10^{−}$ ^{4} or \| ^{r}^{−}}^{ci} $$r$$ $$ci$$ \| ≤ $10^{−}$ ^{4

예제 1

입력

3 3
0.0000000000 0.0000000000
0.0000000000 2.0000000000
2.0000000000 0.0000000000
1 2
2 3
3 1

출력

예제 2

입력

5 4
-0.4585133080 0.2893567973
9.9368007273 7.1806641913
-8.4621834970 -2.8309311865
0.0122121945 -2.8309311865
2.3991780589 -8.8626906628
2 1
3 2
4 3
5 1

출력

예제 3

입력

5 5
0.0000000000 0.0000000000
1.0000000000 2.0000000000
2.0000000000 4.0000000000
3.0000000000 6.0000000000
4.0000000000 8.0000000000
1 2
2 3
3 4
4 5
5 1

출력

NE

설명

Clarification of the first example:
This is the only solution that satisfies all the touching conditions. Please note that solution (0.585700,
1.414357, 1.414357) is also considered correct, even though spaceships 2 and 3 aren’t touching, because
the absolute error doesn’t exceed 10−4.
Clarification of the third example:
There is no arrangement of the radii that satisfies all conditions.

문제 정보

생성자가 기록되지 않았습니다.

출처 COCI 2022/2023 Contest 1

올림피아드 > COCI > 2022/2023 > Contest 1

평가 및 의견

Berilij

개요

출제자 난이도

레이팅 미적용 의견 0 / 50 공개 집계 (커뮤니티 난이도, 주요 주제, 품질)는 의견이 충분히 모이면 공개됩니다.

개별 의견

아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.

풀이 제출

Berilij

게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다. 로그인하고 제출하기

언어

작성 중 Rush? 언어 레퍼런스 읽기 ↗

공개

C++20 Tab 들여쓰기 · Ctrl+/ 주석 토글 · Enter 자동 들여쓰기

행1 열1 1줄 0자 공백: 4 · UTF-8

서브태스크	점수	설명
1	15점	$\(n\)$ is odd, and each of the spaceships should touch exactly two other spaceships.
2	25점	There exists at least one way to determine the radii so the conditions are satisfied.
3	30점	For each pair of spaceships (a, b), there’s at most one sequence of distinct spaceships that starts in $\(a\)$ , and finishes in $\(b\)$ , and all adjacent spaceships in the sequence are necessarily touching.
4	40점	No additional constraints. Your answer will be considered correct if, for each radius of the $\(n\)$ spaceships, its absolute or relative error doesn’t exceed $10^{−}$ ^{4}. In other words, if your answer for the $\(i-th\)$ spaceship is $\(r@@RISE_MATH_BLOCK_0@@ci\)$ , then your answer wil be considered correct if \| $\(r@@RISE_MATH_BLOCK_1@@ci\)$ \| ≤ $10^{−}$ ^{4} or \| ^{r}^{−}}^{ci} $\(r\)$ $\(ci\)$ \| ≤ $10^{−}$ ^{4