Don't use int("smth"), because len of number can be greater than 4000 or use sys.set_int_max_str_digits() if you use python

Edited by author 26.07.2024 17:14

but stack overflow

be careful, you must output the number of stops in the new route k
and  NOT K+1
So, for example in C++
vector<int> res;
...

cout << res.size() - 1 << " "; // check this. not cout << res.size() << " ";


Edited by author 05.01.2014 23:39

U can use Python `eval(expression, variablesDict)` syntax and get easy AC.

Personally, I don’t understand the location of the streets and pedestrian crossings at all. It was hoped that the layout would be based on actual streets. I opened the map, and these two streets are generally parallel... The authors could at least draw a picture for the stupid...

January 1st 1600 is sunday, not monday!

Why can't I construct strings like "aa...a"? There is only one palindrome (the whole string) and it's the minimum value of palindromes obviously. Where is the contradiction the the statement?

1 3
d
c a
a b
b c

I'm the first one, who stuck on this test, my program written in Kotlin (probably, same rules applies to Java).
I don't understand, what is "maximum precision"? Should I use double, float or maybe bigdecimal?

My program calculates side lengths, area of the triangle (via sides), angles (via sides and acos), and result point C_2.

Any help is really welcome!

import kotlin.math.*

class Point(val x: Int, val y: Int) {

    constructor(raw: String) :
            this(raw.split(' ')[0].toInt(), raw.split(' ')[1].toInt())

    override fun toString(): String = "$x $y"
}

class Vector(p1: Point, p2: Point) {
    private val x = p1.x - p2.x
    private val y = p1.y - p2.y
    fun length(): Double = sqrt((x*x + y*y).toDouble())
}

fun angle(v1: Vector, v2: Vector, v3: Vector): Double =
    acos(
        (v1.length().pow(2) + v2.length().pow(2) - v3.length().pow(2))
                / (2 * v1.length() * v2.length())
    )

fun triangleSquare(v1: Vector, v2: Vector, v3: Vector): Double {
    val halvedSideSum = (v1.length() + v2.length() + v3.length()) / 2.0
    return sqrt(
        halvedSideSum *
                (halvedSideSum - v1.length()) *
                (halvedSideSum - v2.length()) *
                (halvedSideSum - v3.length())
    )
}

fun Double.fuzzyEquals(other: Double): Boolean = (abs(this - other) < 1e-10)

fun Double.fuzzyEqualsLow(other: Double): Boolean = (abs(this - other) < 1e-4)

fun main() {
    // input
    val pointA = Point(readln())
    val pointB = Point(readln())
    val pointC = Point(readln())

    // solution
    val fixedPointA = Point(0, 0)
    val fixedPointB = Point(pointB.x - pointA.x, pointB.y - pointA.y)
    val fixedPointC = Point(pointC.x - pointA.x, pointC.y - pointA.y)

    val sideAB = Vector(fixedPointA, fixedPointB)
    val sideBC = Vector(fixedPointB, fixedPointC)
    val sideAC = Vector(fixedPointA, fixedPointC)

    val angleBAC = angle(sideAB, sideAC, sideBC)
    val angleACB = angle(sideAC, sideBC, sideAB)
    val angleCBA = angle(sideBC, sideAB, sideAC)

    // find h
    val h = 2.0 / sideAC.length() * triangleSquare(sideAB, sideBC, sideAC)
    // tan ACB = h / x
    val x = h / tan(angleACB)
    val subtractVectorLength = 2.0 * x
    val ratio = (sideAC.length() - subtractVectorLength) / sideAC.length()

    if (ratio <= 0.0 || ratio.fuzzyEquals(0.0) || ratio.fuzzyEqualsLow(1.0)) println("YES")
    else {
        println("NO")
        println(fixedPointA)
        println(fixedPointB)
        println(
            "%.20f".format(fixedPointC.x * ratio) +
                " ${"%.20f".format(fixedPointC.y * ratio)}")
    }
}

Edited by author 22.07.2024 22:53

a < b и p1 = q1, p2 = q2, …, pa = qa.

3 3
a
b
c
a d
b e
c f

Please give me some test that can help me

The test contents points entered clockwise, which doesn't respond the condition.
I succeed passing the test only after applied an algo, which is not sesitive to the order of points in polygone

Edited by author 29.04.2024 19:57

Edited by author 29.04.2024 19:57

Try not to use double, probably there is something like ceil(log(n)) = ceil(1.000000000000000000000001) = 2.0

Also in test 6 N is greater than 1.000.000.

I used Int and Float data types and got AC

 Type
>   Point               =record
>     x,y,d             :real;
>     ID                :Integer;
>   end;
> Var
>   a                   :array[0..1000] of point;
>   n,i                 :integer;
>
> function partition(first,last:integer):integer;
> Var
>   t                   :point;
>   i,j                 :integer;
>   x                   :real;
> begin
>   i:=first-1;
>   j:=last+1;
>   x:=a[first].d;
>   while true do
>   begin
>     repeat inc(i);
>     until a[i].d<=x;
>     repeat dec(j);
>     until a[j].d>=x;
>     if i<j then begin
>       t:=a[i]; a[i]:=a[j]; a[j]:=t; end
>     else begin
>       partition:=j; exit; end;
>   end;
> end;
>
> Procedure qsort(first,last:integer);
> Var
>   w                   :integer;
> begin
>   if first<last then
>   begin
>     w:=partition(first,last);
>     qsort(first,w);
>     qsort(w+1,last);
>   end;
> end;
>
> Function ATG(x:integer):real;
> Var
>   dx,dy,k             :real;
> begin
>   dx:=a[x].x-a[0].x;
>   dy:=a[x].y-a[0].y;
>   if dx=0 then
>     k:=90
>   else
>     k:=arctan(dy/dx)/pi*180;
>   if (k<0) or ((k=0) and (dx<0)) then k:=k+180;
>   if dy<0 then k:=k+180;
>   atg:=k;
> end;
>
> begin
>   readln(a[0].x,a[0].y);
>   readln(n);
>   for i:=1 to n do
>   begin
>     readln(a[i].x,a[i].y,a[i].ID);
>     a[i].d:=ATG(i);
>   end;
>   qsort(1,n);
>   writeln(0);
>   for i:=1 to n do
>     writeln(a[i].Id);
>   writeln(0);
> end.

use epsilon 4.6e-9

7 4
6 4
5 3
7 5
8 6

1 1
1 1

you print Ask Shiftman for help. once again, although the correct answer is Perfect

1 0 0 0