Problem Link

Description: A set of points P and a set of target points M in 2D space are given,. For each point M[i] in M, find the minimum angle at M[i] such that all the points P[i] in P are contained within this angle. If the angle is not less than 180 degrees, then you just have to output “TOO WIDE”.

Constraints: 1<= N,Q <=100000

My approach: First I find the convex hull and then check if the query point is in the convex hull. If it is in the polygon then the answer will be "TOO WIDE" . If not then I do as follows:

Find the centroid of the polygon and then find the angle of the vector "centroid to Pi" with x axis, where Pi represent points of the convex polygon.

Eg. if centroid =(0,0) and Pi=(1,1) is one of the points of polygon then the angle of the centroid to Pi vector is 45 degree. If Pi=(-1,-1) then the angle = 225 degree.

Then sort the points with respect to their angle. When I got a query point M then I again calculate the angle of the vector "centroid to query point M". Now I cut the polygon into two half with the line passes through the centroid and M. Then for each half I do ternary search and finally find the point X and Y as shown in the figure.

[In figure , C=centroid , M=query point and black lines represent the convex polygon]

Thus I find the angle (X,M,Y). But my approach is seemed to be incorrect and I cannot figure out what I do wrong here. Was my approach correct? Is there any other approach to solve this problem?

-Thanks in advance.

I am currently solving ACM Timus 2058 , a problem about palindromes.

In palindromic tree every node represents a distinct palindrome (lets say , p) in a string and this node links to another node which represents the longest proper suffix of it(p) which is a palindrome. Eg. If a node u represents "aabaa" then it's link will be a node v which represents "aa", since "aa" is longest palindromic suffix of "aabaa".

When solving that problem, I observed an interesting property (and I could not prove it's correctness) about palindrome.

 [  Note : If X is a string , then here by (X^n) I mean concatenation of n X string.  If X="ab" then X^3= "ababab".  And XY represent concatenation of X and Y . X="a" ,Y="b" then XY="ab" ] 

Property-1: " If a palindrome P has longest palindromic suffix Q and if | length of Q | >= (| length of P | / 2) then palindrome P has a structure like (X^n)Y where n>=2 , X and Y are string ( | Y | < | X | and Y could be a null string ). Here, X will be a prefix of P and length of X= |P|-|Q|. "

Eg-1 : If X='aba' and Y=''(NULL) then 'abaaba' = (X^2), 'abaabaaba' = (X^3), 'abaabaabaaba = (X^4)' etc If X='bba' and Y='bb' then 'bbabbabb' = [(X^2)Y], 'bbabbabbabb' = [(X^3)Y] , 'bbabbabbabbabb' = [(X^4)Y] etc

EG (of property): P="bbabbabbabb" and longest suffix palindrome of it is Q="bbabbabb" then by property X="bba". Now P can be represent as XXXY, where Y="bb" .

And then Y would be a palindrome too.

But everything depends on Property-1. I did some paper works and found it happens. But I think it is not enough to find the correctness of the property.

Edit: This property is correct, as symbols on positions that differs by |P| - |Q| are equal ( Thanks Um_nik for providing the proof).

Why symbols on positions that differs by |P|-|Q| would be equal? You can find the proof here

[ Sorry For my bad English. I tried my best to explain ,though I am not good at explaining. If you don't understand any part of it , you can ask me ]

Problem Link: Chor Tintin Tikri

Note: Actually the problem contain wrong statement .Here 0<=Edge<=5000 .

Input: 
4 6
1 2
1 3
1 4
2 3
2 4
3 4
           __1__
         _/  |  \_
       _/    |    \_
     _/   ___3__    \_
   _/   _/      \_    \
  2 ___/___________\___4

In this graph , every vertices is a part of some triangles. And Adjacent of nodes(1,2 4) make a cycle of odd length and thus the output will be 4.

And got many wrong answer using this approach. Can anyone suggest any hint please or solution ? Thanks in Advance.

removed after AC