PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: tautsjasiunsas
Tester: alei_adm
Editorialist: tautsjasiunsas
DIFFICULTY:
MEDIUM-HARD?
PREREQUISITES:
Geometry, 2-pointers
PROBLEM:
Given a polyline P, find a direction v such that all indices i with v \cdot (P_{i+1}-P_i) > 0 form a subsegment and none are equal to 0.
QUICK EXPLANATION:
First, create an array A_i = P_i- P_{i+1}.
After, make a vector S storing all A_i, -A_i, (0,1), (0,-1), (1,0), (-1,0).
Sort S by polar angle.
Iterate over S, let (x, y) = S_i + S_{i+1}, check (y, -x) for an answer.
This gives O(n^2) solution. To make it faster use 2-pointers.
EXPLANATION:
If we look at the formula of dot product: v \cdot a = |v|\cdot|a|\cdot cos(\alpha).
Let’s imagine we sweep through all possible v (with real coordinates, v = (\cos(\theta), \sin(\theta))).
It is easy to see that the sign of v \cdot (P_{i+1}-P_i) changes then it is 0.
It can only be 0 iff angle(a)= \theta\pm\pi/2. We can create those v by rotating P_{i+1}-P_i 90 degrees clockwise and counterclockwise.
Let’s add all those vectors to a candidate list S.
Sort S, so that \theta is increasing (and remove duplicates).
If we iterate over S and check a vector with \theta between S_i and S_{i+1} we would find an answer. (S_i can never be an answer)
If we add (0,1), (0, -1), (1,0), (-1,0) to S, an angle between S_i and S_{i+1} is at most 90. This means that S_i+S_{i+1} angle will always be between S_i and S_{i+1} (and have integer coordinates), checking all those vectors would give O(n^2) solution.
Let’s make our solution faster.
After we created all the candidate answers in O(n\log(n)), we should sort array A_i by polar angle. While we iterate over candidate answers, it is easy to maintain 2-pointers l,r, such that all the indices with positive dot product are in the interval [l, r]. To check if an answer is valid we should check if the original indices form a continuous subsegment max - min = r - l.
SOLUTIONS:
Setter's Solution
/*input
1
7
500000000 0
0 500000000
0 0
0 -500000000
-500000000 0
-500000000 -500000000
500000000 500000000
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//point struct and basic operations
struct point
{
ll x, y;
point() {x = 0; y = 0;}
point(ll x, ll y): x(x), y(y) {}
int quarter()const
{
if (x >= 0 && y >= 0)
return 0;
if (x <= 0 && y >= 0)
return 1;
if (x <= 0 && y <= 0)
return 2;
if (x >= 0 && y <= 0)
return 3;
assert(false);
return -1;
}
};
point operator-(const point &a, const point &b)
{
return point(a.x - b.x, a.y - b.y);
}
point operator+(const point &a, const point &b)
{
return point(a.x + b.x, a.y + b.y);
}
ll cross(const point &a, const point &b)
{
return a.x * b.y - a.y * b.x;
}
ll dot(const point &a, const point &b)
{
return a.x * b.x + a.y * b.y;
}
//comparator for sorting A and X
bool operator<(pair<point, int> c, pair<point, int> d) {
if (c.first.quarter() != d.first.quarter())
return c.first.quarter() < d.first.quarter();
ll cr = cross(c.first, d.first);
if (cr != 0)
return cr > 0;
else
return c.second < d.second;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
assert(1 <= t && t <= 5);
while (t–)
{
int n;
cin >> n;
assert(n >= 3 && n <= 100000);
vectorP(n + 1);
for (int i = 0; i < n; i++)
{
cin >> P[i].x >> P[i].y;
assert(abs(P[i].x) <= 500000000);
assert(abs(P[i].y) <= 500000000);
}
P[n] = P[0];
//storing all points in a sorted vector
vector<pair<point, int>>A;
for (int i = 0; i < n; i++)
{
A.push_back({P[i] - P[i + 1], i});
A.push_back({P[i + 1] - P[i], -1});
}
//adding some more vectors so A[i]+A[i+1] would work properly
for (int x = -1; x <= 1; x++)
{
for (int y = -1; y <= 1; y++)
{
if (x != 0 || y != 0)
A.push_back({point(x, y), -1});
}
}
sort(A.begin(), A.end());
//X[side][quarter]
//Y[side]
set<pair<point, int>>X[3][4];
set<int>Y[3];
for (auto i : A)
{
if (i.second != -1)
{
X[0][i.first.quarter()].insert(i);
Y[0].insert(i.second);
}
}
A.push_back(A[0]);
for (int i = 0; i + 1 < (int)A.size(); i++)
{
point v = A[i].first + A[i + 1].first;
//0 -> >0
//1 -> <0
//2 -> =0
auto s = [&](pair<point, int>a)
{
ll val = cross(v, a.first);
if (val > 0)
return 0;
if (val < 0)
return 1;
return 2;
};
for (int c = 0; c < 3; c++)
{
for (int k = 0; k < 4; k++)
{
while (!X[c][k].empty())
{
auto it = X[c][k].begin();
if (s(*it) != c)
{
Y[s(*it)].insert(it->second);
Y[c].erase(it->second);
X[s(*it)][k].insert(*it);
X[c][k].erase(it);
continue;
}
it = --X[c][k].end();
if (s(*it) != c)
{
Y[s(*it)].insert(it->second);
Y[c].erase(it->second);
X[s(*it)][k].insert(*it);
X[c][k].erase(it);
continue;
}
break;
}
}
}
bool ok = false;
if (Y[2].empty())
{
for (int t : {0, 1})
{
assert(!Y[t].empty());
int sz = Y[t].size();
int diff = (*(--Y[t].end())) - (*Y[t].begin()) + 1;
if (diff == sz)
{
cout << v.y << " " << -v.x << "\n";
goto GG;
}
}
}
}
cout << "0 0\n";
GG:;
}
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int _ = 2e5 + 7; int T , N;
struct comp{
int x , y , id; comp(int _x = 0 , int _y = 0) : x(x) , y(y){}
friend comp operator +(comp p , comp q){return comp(p.x + q.x , p.y + q.y);}
friend comp operator -(comp p , comp q){return comp(p.x - q.x , p.y - q.y);}
friend long long operator %(comp p , comp q){return 1ll * p.x * q.y - 1ll * p.y * q.x;}
friend long long operator *(comp p , comp q){return 1ll * p.x * q.x + 1ll * p.y * q.y;}
friend bool operator <(comp p , comp q){
bool fp = p.y < 0 || (p.y == 0 && p.x < 0) , fq = q.y < 0 || (q.y == 0 && q.x < 0);
return fp == fq ? p % q > 0 : fp > fq;
//return atan2(p.y , p.x) < atan2(q.y , q.x);
}
}P[] , dir[];
bool check(vector < comp > now , comp cur){
for(auto t : now) if(cur * t <= 0) return 0;
return 1;
}
signed main(){
for(cin >> T ; T ; --T){
cin >> N; for(int i = 1 ; i <= N ; ++i) cin >> P[i].x >> P[i].y;
P[N + 1] = P[1]; for(int i = 1 ; i <= N ; ++i){dir[i] = P[i + 1] - P[i]; dir[i].id = i;}
sort(dir + 1 , dir + N + 1); dir[0] = dir[N]; for(int i = 1 ; i <= N ; ++i) dir[i + N] = dir[i];
int pl = 1 , pr = 1; comp ans; set < int >in;
while(pr < 2 * N){
if(in.size() && *–in.end() - *in.begin() == in.size() - 1){
vector < comp > now; now.push_back(dir[pl]); now.push_back(dir[pr - 1]);
now.push_back(comp() - dir[pr]); now.push_back(comp() - dir[pl - 1]);
for(int i = 0 ; i < 4 ; ++i)
for(int j = 0 ; j < 4 ; ++j)
if(check(now , i == j ? now[j] : comp(now[j].y - now[i].y , now[i].x - now[j].x)))
ans = i == j ? now[j] : comp(now[j].y - now[i].y , now[i].x - now[j].x);
}
if(dir[pr] % dir[pl] > 0 || (dir[pr] % dir[pl] == 0 && dir[pr] * dir[pl] < 0)) in.erase(dir[pl++].id);
else in.insert(dir[pr++].id);
}
if(ans.x || ans.y){
in.clear();
for(int i = 1 ; i <= N ; ++i){
assert(dir[i] * ans != 0);
if(dir[i] * ans > 0) in.insert(dir[i].id);
}
assert(*--in.end() - *in.begin() == in.size() - 1);
}
assert(abs(ans.x) <= 2e9 && abs(ans.y) <= 2e9);
cout << ans.x << ' ' << ans.y << endl;
}
return 0;
}
