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

I pass this problem with Sieve of Eratosthenes, but i think solution with Pollard's rho algorithm is funnier, and wrote it too.

If you cant pass it with this algo just use all prime modules from 1'000'000'007 to 1'000'001'393.

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

1 0 0 0