Треугольник

시간 제한2초메모리 제한1024 MB

요약

삼각형과 목표 넓이 S가 주어질 때, 각 변 위의 세 점을 골라 넓이가 S인 삼각형을 만든다.

난이도: 보통10점 중 7점
유형: 기하, 수학, 이분 탐색
정답자: 아직 제출이 없습니다

문제

Задан треугольник и число $S$ . Необходимо на сторонах треугольника выбрать три точки так, чтобы образуемый ими треугольник имел площадь $S$ .

입력

В первой строке входного дано шесть целых чисел $x\_1$ , $y\_1$ , $x\_2$ , $y\_2$ , $x\_3$ , $y\_3$ --- координаты вершины треугольника, все координаты по модулю не превосходят $1000$ . Во второй строке находится целое число $S$ --- площадь, которую необходимо получить ( $0 \le S \le 10^9$ ).

출력

Если точки выбрать нельзя, то выведите <<No solution>>, иначе выведите шесть чисел $x\_1'$ , $y\_1'$ , $x\_2'$ , $y\_2'$ , $x\_3'$ , $y\_3'$ ---координаты вершин нового треугольника. Точки должны отстоять от сторон треугольника не более чем на $10^{-5}$ . Площадь выведенного треугольника должна отличатся от искомой не более чем на $10^{-5}$ .

힌트

В первом примере ответ может выглядеть так:

예제2

예제 1
입력
```
0 0 7 0 0 7
6
```
예상 출력
```
3.0 0.0
3.0 4.0
0.0 4.0
```
예제 2
입력
```
0 0 3 0 0 4
7
```
예상 출력
```
No solution
```