F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Dusk Moon

Time Limit: 11000/11000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 367    Accepted Submission(s): 72


Problem Description
You are given $n$ points $p_1,p_2,\dots,p_n$ on the 2D plane. You need to perform $q$ operations. Each operation is one of the following:

  • ''$\texttt{1 k x y}$'' ($1 \leq k \leq n$, $1\leq x,y\leq 10^8$): Change the coordinate of the point $p_k$ into $(x,y)$.
  • ''$\texttt{2 l r}$'' ($1 \leq l\leq r\leq n$): Find the minimum non-negative integer $R$ such that you can cover all the points $p_l,p_{l+1},\dots,p_r$ using a single circle whose radius is $R$.

  • Note that a point is considered to be covered if and only if it is inside the circle or on the border of the circle.
     

    Input
    The first line contains a single integer $T$ ($1 \leq T \leq 3$), the number of test cases. For each test case:

    The first line of the input contains two integers $n$ and $q$ ($1 \leq n,q \leq 100\,000$), denoting the number of points and the number of operations.

    In the next $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($1\leq x_i,y_i\leq 10^8$), describing the coordinate of $p_i$.

    Each of the next $q$ lines describes an operation in formats described in the statement above.

    It is guaranteed that all the values of $x_i$, $y_i$, $x$, $y$ are chosen uniformly at random from integers in their corresponding ranges. The randomness condition does not apply to the sample test case, but your solution must pass the sample as well.
     

    Output
    For each query, print a single line containing an integer, denoting the minimum radius.
     

    Sample Input
    1 5 5 1 1 2 2 3 1 3 3 2 5 2 1 5 2 1 1 2 1 2 1 1 10 1 2 1 5
     

    Sample Output
    3 0 1 5
     

    Source
     

    Statistic | Submit | Discuss | Note
    Hangzhou Dianzi University Online Judge 3.0
    Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
    Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
    Total 0.000000(s) query 1, Server time : 2024-03-29 17:17:26, Gzip enabled