QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#463058 | #8468. Collinear Arrangements | LR | WA | 1ms | 3560kb | C++20 | 3.8kb | 2024-07-04 12:51:08 | 2024-07-04 12:51:08 |
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];
/**
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;
}
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 >> x.ff >> x.ss;
if (t == 1)
{
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
{
set<int> ans;
cin >> y.ff >> y.ss;
int l = 1, r = n;
while (l <= r)
{
int mid = (l + r) / 2;
if (cw(x, y, a[mid])) l = mid + 1;
else if (ccw(x, y, a[mid])) r = mid - 1;
else
{
ans.emplace(mid);
break;
}
}
l = 1, r = n;
while (l <= r)
{
int mid = (l + r) / 2;
if (cw(x, y, a[mid])) r = mid - 1;
else if (ccw(x, y, a[mid])) l = mid + 1;
else
{
ans.emplace(mid);
break;
}
}
l = 1, r = n;
while (l <= r)
{
int mid = (l + r) / 2;
if (cw(y, x, a[mid])) l = mid + 1;
else if (ccw(y, x, a[mid])) r = mid - 1;
else
{
ans.emplace(mid);
break;
}
}
l = 1, r = n;
while (l <= r)
{
int mid = (l + r) / 2;
if (cw(y, x, a[mid])) r = mid - 1;
else if (ccw(y, x, a[mid])) l = mid + 1;
else
{
ans.emplace(mid);
break;
}
}
cout << ans.size() << "\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3488kb
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: 3532kb
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: 1ms
memory: 3560kb
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:
1
result:
wrong answer 1st numbers differ - expected: '2', found: '1'