QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#466809 | #8468. Collinear Arrangements | LR | WA | 0ms | 3756kb | C++14 | 4.8kb | 2024-07-08 10:18:45 | 2024-07-08 10:18:49 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define ff first
#define ss second
using namespace std;
const int maxn = 2e5 + 5;
int n, q;
ii a[maxn];
inline int read()
{
char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
if(nega==-1) return -ans;
return ans;
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l, int r)
{
uniform_int_distribution<int> rg(l, r);
return rg(rng);
}
/**
A, B, C collinear
when
(Ax - Bx) / (Ay - By) == (Bx - Cx) / (By - Cy)
**/
bool cw(ii &a, ii &b, ii &c)
{
int ans = (b.ff - a.ff) * (b.ss + a.ss) + (c.ff - b.ff) * (c.ss + b.ss) + (a.ff - c.ff) * (a.ss + c.ss);
return ans > 0;
}
bool ccw(ii &a, ii &b, ii &c)
{
int ans = (b.ff - a.ff) * (b.ss + a.ss) + (c.ff - b.ff) * (c.ss + b.ss) + (a.ff - c.ff) * (a.ss + c.ss);
return ans < 0;
}
bool collinear(ii &a, ii &b, ii &c)
{
int ans = (b.ff - a.ff) * (b.ss + a.ss) + (c.ff - b.ff) * (c.ss + b.ss) + (a.ff - c.ff) * (a.ss + c.ss);
return ans == 0;
}
void inc(int &x) {
x++;
if (x > n) x -= n;
}
int inc2(int x, int y) {
x += y;
if (x > n) x -= n;
return x;
}
bool binsearch(int u, int v, ii x, ii y) {
if (u >= v) v += n;
int l = u; int r = v - 1;
if (cw(x, y, a[l])) swap(x, y);
while (l <= r) {
int mid = (l + r) / 2;
if (collinear(x, y, a[mid])) return 1;
if (ccw(x, y, a[mid])) l = mid + 1;
else r = mid - 1;
}
return 0;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i].ff >> a[i].ss,
a[i + n] = a[i];
while (q--)
{
int t; ii x, y;
cin >> t;
if (t == 1)
{
cin >> x.ff >> x.ss;
int ans = 0;
for (int i = 1; i <= n; i++)
{
int l = i + 1, r = i + n - 1, yes = 0;
while (l <= r)
{
int mid = (l + r) / 2;
if (cw(a[i], x, a[mid])) l = mid + 1;
else if (ccw(a[i], x, a[mid])) r = mid - 1;
else
{
yes = mid;
break;
}
}
l = i + 1, r = i + n - 1;
while (l <= r)
{
int mid = (l + r) / 2;
if (cw(a[i], x, a[mid])) r = mid - 1;
else if (ccw(a[i], x, a[mid])) l = mid + 1;
else
{
yes = mid;
break;
}
}
ans += yes > 0;
}
cout << ans / 2 << "\n";
}
else
{
cin >> x.ff >> x.ss >> y.ff >> y.ss;
int u, ans;
while (true) {
int root = rand(1, n);
while (collinear(a[root], x, y)) inc(root);
u = root;
int l = 1; int r = n - 1;
if (cw(x, y, a[root])) swap(x, y);
ii XY = {y.ff-x.ff, y.ss-x.ss};
ii normal_vec = {-XY.ss, XY.ff};
ii root2 = {a[root].ff - normal_vec.ff, a[root].ss - normal_vec.ss};
ans = -1;
// cout << normal_vec.ff<<','<<normal_vec.ss<<'\n';
// cout << root2.ff<<','<<root2.ss<<'\n';
while (l <= r) {
int mid = (l + r) / 2;
int v = inc2(u, mid);
bool Up = !cw(a[root], root2, a[v]);
bool Down = !ccw(a[root], root2, a[v]);
bool Left = !cw(x, y, a[v]);
bool Right = !ccw(x, y, a[v]);
// cout << v << " := " << Up << ' ' << Down << ' ' << Left << ' ' << Right << '\n';
if ((Up && Right) || (Down && Right) || (Down && Left)) {
ans = v;
l = mid + 1;
}
else r = mid - 1;
}
if (ans != -1) break;
}
int v = ans; int res = 0;
if (u == v) res = binsearch(u, v, x, y);
else res = binsearch(u, v, x, y) + binsearch(v, u, x, y);
// cout << u << " -> " << v << '\n';
cout << res << '\n';
}
}
}
/**
5 1
0 0
2 0
2 1
1 2
0 2
2 1 1 2 2
**/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3748kb
input:
5 3 0 0 2 0 2 1 1 2 0 2 1 1 1 2 1 1 2 2 1 2 2
output:
1 1 2
result:
ok 3 number(s): "1 1 2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
3 1 0 0 1 0 0 1 2 1 1 2 2
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3756kb
input:
1000 1 -139438978 -172098481 -125097652 -169056403 155419484 -28898293 186215972 6874955 240691742 77644763 334255616 236444333 342049790 274206233 342049766 274611851 342049472 275025569 342049298 275242193 342048794 275724449 341967248 297262013 341966000 297569423 341963012 298092233 341960624 29...
output:
0
result:
wrong answer 1st numbers differ - expected: '2', found: '0'