# algorithms – find the vector v

Chef John is given N points P1,P2,…,PN in a plane. For each valid i, the coordinates of the point Pi are (xi,yi). Help him find a vector v→=(xv,yv) such that the following holds:

For each i (1≤i≤N), let Si=v→⋅PiPi+1. Here, we define Pn+1=P1.
The coordinates xv and yv are integers and |xv|,|yv|≤2⋅109.
It is possible to find three integers w, l and r (1≤l≤r≤N) such that:
For each i (l≤i≤r), Siw>0.
For each other valid i, Siw<0.
If there are multiple solutions, you may find any one. If there are no solutions, let’s define xv=yv=0. (Note that the vector v→=(0,0) cannot be a valid solution.)