QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#466228 | #8468. Collinear Arrangements | LR | WA | 0ms | 8756kb | C++20 | 4.4kb | 2024-07-07 17:02:47 | 2024-07-07 17:02:47 |
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;
}
struct Vec
{
int x,y;
Vec(int a=0,int b=0) {x=a,y=b;}
};
Vec operator + (const Vec &x,const Vec &y) {return Vec(x.x+y.x,x.y+y.y);}
Vec operator - (const Vec &x,const Vec &y) {return Vec(x.x-y.x,x.y-y.y);}
Vec operator * (const Vec &x,const int y) {return Vec(x.x*y,x.y*y);}
Vec operator / (const Vec &x,const int y) {return Vec(x.x/y,x.y/y);}
int cdot(const Vec &x,const Vec &y) {return x.x*y.x+x.y*y.y;}
int cross(const Vec &x,const Vec &y) {return x.x*y.y-x.y*y.x;}
int norm(Vec x) {return x.x*x.x+x.y*x.y;}
Vec rot90(Vec x) {return Vec(x.y,-x.x);}
Vec A[maxn];
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];
for (int i = 1; i <= n * 2 + 1; i++)
A[i] = Vec(a[(i - 1) % n + 1].ff, a[(i - 1) % n + 1].ss);
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
{
Vec P,Q;
cin >> P.x >> P.y >> Q.x >> Q.y;
Vec v=rot90(Q-P);
int orig=1;
while(cdot(A[orig+1]-A[orig],v)==0) orig++;
int c1=orig;
if(cdot(A[c1+1]-A[c1],v)<0) v=v*(-1);
// printf("%d %d\n",v.x,v.y);
for(int i=17;i>=0;i--)
{
if(c1+(1<<i)<=orig+n-1)
{
int tw=c1+(1<<i);
if(cdot(v,A[tw+1]-A[tw])>0&&cdot(v,A[tw]-A[c1])>=0) c1+=(1<<i);
}
}
c1=c1%n+1;
int c2=c1;
v=v*(-1);
// printf("%d %d\n",v.x,v.y);
// cout<<cdot(v,A[tw]-A[i])<<endl;
for(int i=17;i>=0;i--)
{
if(c2+(1<<i)<=c1+n-1)
{
int tw=c2+(1<<i);
if(cdot(v,A[tw+1]-A[tw])>0&&cdot(v,A[tw]-A[c2])>=0) c2+=(1<<i);
}
}
c2++;
// printf("%d %d\n",c1,c2);
auto find=[&](int l,int r)->int
{
int o=cross(Q-P,A[l]-P);
if(o==0) return 1;
while(l<=r)
{
int mid=(l+r)/2;
int tw=cross(Q-P,A[mid]-P);
if(tw==0) return 1;
if((tw>0)==(o>0)) l=mid+1;
else r=mid-1;
}
return 0;
};
int ans=0;
ans+=find(c1+1,c2);
ans+=find(c2+1,c1+n);
printf("%lld\n",ans);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 8756kb
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 2 1
result:
wrong answer 2nd numbers differ - expected: '1', found: '2'