Hint #1: The mouse or the cheese can be less than 10cm from the polygons
Hint #2: Be careful of your first segment from the mouse or the last segment from the cheese. If you do not check correctly, they might cross a polygon. For example, think of the case of a very thin rectangle with the long side called A and a mouse that is less than 10cm from the rectangle. You have to make sure that the mouse runs to side A not the side opposite to A.

this is bug, it is imposible.

if i have n = 1 and k = 10000, i need two minutes

I've this test wrong too. Here's my code:

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <ctime>
using namespace std;

#define forn(i,n) for (int i = 0; i < (int)n; i++)

struct bus {
    int l, r, type, num;
    friend bool operator<(const bus &bus1, const bus &bus2) {
        if (bus1.type != bus2.type) {
            return bus1.r < bus2.r;
        } else {
            return bus1.num < bus2.num;
        }
    }
};

int n, m;
vector<pair<int, int> > v1, v2;
bus mas[300000];

multiset<bus> s;
multiset<bus>::iterator iter;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    scanf("%d", &n);
    v1.resize(n);
    forn(i,n) {
        scanf("%d%d", &v1[i].first, &v1[i].second);
        v1[i].second += v1[i].first - 1;
    }
    scanf("%d", &m);
    v2.resize(m);
    forn(i,m) {
        scanf("%d%d", &v2[i].first, &v2[i].second);
        v2[i].second += v2[i].first - 1;
    }
    for (int i = 1; i <= n; i++) {
        mas[i].l = v1[i - 1].first;
        mas[i].r = v1[i - 1].second;
        mas[i].type = 1;
        mas[i].num = i;
    }
    for (int i = 1; i <= m; i++) {
        mas[i + n].l = v2[i - 1].first;
        mas[i + n].r = v2[i - 1].second;
        mas[i + n].type = 2;
        mas[i + n].num = i;
    }
    int p1 = 1, p2 = n + 1;
    int t = min(mas[p1].l, mas[p2].l);
    while ((p1 <= n && p2 <= m + n) || t <= 230000000) {
        while (p1 <= n && mas[p1].l <= t) {
            if (mas[p1].r < t) {
                printf("NO");
                return 0;
            } else {
                s.insert(mas[p1++]);
            }
        }
        while (p2 <= m + n && mas[p2].l <= t) {
            if (mas[p2].r < t) {
                printf("NO");
                return 0;
            } else {
                s.insert(mas[p2++]);
            }
        }
        iter = s.begin();
        if (iter != s.end()) {
            if ((*iter).r < t) {
                printf("NO");
                return 0;
            } else {
                s.erase(iter);
            }
            t++;
        } else {
            t = 230000000;
            if (p1 <= n) {
                t = min(t, mas[p1].l);
            }
            if (p2 <= n + m) {
                t = min(t, mas[p2].l);
            }
            if (t == 230000000) {
                printf("YES");
                return 0;
            }
        }
    }
    printf("YES");
    //printf("%.5lf", 1.0 * clock() / (1.0 * CLOCKS_PER_SEC));
}

Where's bug?

1
1 3
2
1 4
1 2

answer is "YES"

To kill the weakest 3 coins with one spell it would have to have spell power 2, which means you get 3*2 = 6 > 4 damage reflected.

At first sight, I strongly suggest you to avoid operating repeteadly with floating points, the little errors will accummulate, and WA comes to the order.

at second sight the logic is just not right. Look, I got the same algorithm that a dude with TLE at test9, but with a less complex break condition.

private static int sq(long A,long N){
    double aux= Math.sqrt( ((A*A)<<2) - (A<<2) + 1 + 8*N);
    int r = (int)aux;
    if ((double)r==aux)
        return r;
    else
        return -1;
    }
    public static void main (String[]args){
        Scanner s=new Scanner(System.in);
        int N= s.nextInt();
        long A=1,P=1,root=0;
        while (true){
            root= sq(A,N);
            if (root==-1)
                A++;
            else{
                P= (1-(A<<1)+root)/2;
                break;
            }
        }
        System.out.println(A+" "+(P));
    }

The running time of a simple backtracking search will depend on the move search order you use.

For example, this order:

moves = [ a, e, f, b, c, g, h, d ]
  where a = (1,-2)
        b = (1,2)
        c = (-1,2)
        d = (-1,-2)
        e = (2,1)
        f = (2,-1)
        g = (-2,1)
        h = (-2,-1)

works great for n = 7, but not 6 or 8.