QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#848986 | #8468. Collinear Arrangements | CarroT1212 | WA | 5ms | 5904kb | C++14 | 3.4kb | 2025-01-09 11:06:43 | 2025-01-09 11:06:47 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
using lin=pair<pll,pll>;
const int I=1e9;
const ll J=1e18,N=2e5+7;
ll n,q,st[N],sz;
ld k[N];
pll a[N];
map<ll,ll> mp;
ll operator * (pll x,pll y) { return x.x*y.y-x.y*y.x; }
pll operator * (pll x,ll y) { return {x.x*y,x.y*y}; }
pll operator + (pll x,pll y) { return {x.x+y.x,x.y+y.y}; }
pll operator - (pll x,pll y) { return {x.x-y.x,x.y-y.y}; }
ld gk(pll x) { return x.x?(ld)x.y/(ld)x.x:J; }
ld len(pll x) { return sqrt((ld)x.x*x.x+x.y*x.y); }
ll chk(lin x,lin y) {
pll xx=x.y-x.x,yy=y.y-y.x,zz=x.y-y.y;
if (xx*yy==0) return yy*zz==0;
ld t=(ld)(zz*yy)/(ld)(xx*yy);
// printf(" (%lld,%lld)-(%lld,%lld) & (%lld,%lld)-(%lld,%lld) %Lf\n",x.x.x,x.x.y,x.y.x,x.y.y,
// y.x.x,y.x.y,y.y.x,y.y.y,t);
return t<1?2:t==1?1:0;
}
ll solve(lin l) {
if (l.x.x==l.y.x) return mp[l.x.x];
ld lk=gk(l.y-l.x); ll ret=0;
ll cl=upper_bound(k+st[0],k+st[1],lk)-k,cr=lower_bound(k+st[1],k+st[2],lk)-1-k;
ll dl=upper_bound(k+st[1],k+st[2],lk)-k,dr=lower_bound(k+st[2],k+st[3],lk)-1-k;
// printf("(%lld,%lld)-(%lld,%lld)\n",l.x.x,l.x.y,l.y.x,l.y.y);
// printf("%lld %lld %lld %lld\n",cl,cr,dl,dr);
if (cr+1<dl&&(a[dl]-a[cr+1])*(l.x-a[dl])==0) ret++;
if (dr+1<cl+n&&(a[cl+n]-a[dr+1])*(l.x-a[cl+n])==0) ret++;
while (cl<=cr) {
ll mid=cl+cr>>1,w=chk({a[mid],a[mid+1]},l);
if (w==1) { ret++; break; }
else if (w==2) cl=mid+1;
else cr=mid-1;
}
while (dl<=dr) {
ll mid=dl+dr>>1,w=chk({a[mid],a[mid+1]},l);
if (w==1) { ret++; break; }
else if (w==2) dl=mid+1;
else dr=mid-1;
}
// printf(" %lld\n",ret);
return ret;
}
void mian() {
scanf("%lld%lld",&n,&q);
for (ll i=0;i<n;i++) scanf("%lld%lld",&a[i].x,&a[i].y),mp[a[i].x]++,a[n+i]=a[i];
a[n*2]=a[0];
for (ll i=0;i<n*2;i++) k[i]=gk(a[i+1]-a[i]);
if (k[0]<k[n-1]) st[sz++]=0;
for (ll i=1;i<n*2;i++) if (k[i]<k[i-1]) st[sz++]=i;
// for (ll i=0;i<n*2;i++) printf("%.1Lf ",k[i]); printf("\n");
// printf("%lld %lld %lld %lld\n",st[0],st[1],st[2],st[3]);
for (ll opt;q--;) {
scanf("%lld",&opt);
pll s,t;
if (opt==1) {
scanf("%lld%lld",&s.x,&s.y);
// ll ans=0;
// for (ll i=0;i<n;i++) ans+=solve({s,a[i]})==2;
// cout<<ans/2<<"\n";
ll flg=1,ans=0;
for (ll i=0;i<n;i++) if ((a[i+1]-a[i])*(s-a[i])<0) flg=0;
if (flg) {
// printf("114514\n");
for (ll i=0,j=0;i<n;i++) {
while ((a[j+1]-a[i])*(s-a[i])>=0) j++;
if (i!=j&&(a[j]-a[i])*(s-a[i])==0) ans++;
}
ans/=2;
}
else {
ld d=J; ll p=0,pp;
for (ll i=0;i<n;i++) {
ld dd=len(a[i]-s);
if (dd<d) d=dd,p=i;
}
for (pp=(p+1)%n;(a[p]-s)*(a[pp]-s)<0;pp=(pp+1)%n);
// printf("%lld %lld\n",p,pp);
if ((a[p]-s)*(a[pp]-s)==0) ans++;
for (ll i=(p+1)%n,j=pp;;i=(i+1)%n) {
while ((a[i]-s)*(a[j]-s)>0) j=(j+n-1)%n;
if (i==j) break;
if ((a[i]-s)*(a[j]-s)==0) ans++;
}
for (ll i=(p+n-1)%n,j=pp;;i=(i+n-1)%n) {
while ((a[i]-s)*(a[j]-s)<0) j=(j+1)%n;
if (i==j) break;
if ((a[i]-s)*(a[j]-s)==0) ans++;
}
}
cout<<ans<<"\n";
}
else {
scanf("%lld%lld%lld%lld",&s.x,&s.y,&t.x,&t.y);
cout<<solve({s,t})<<"\n";
}
}
}
bool ORY; int main() {
// while (1)
// int t; for (scanf("%d",&t);t--;)
mian();
cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5824kb
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: 1ms
memory: 5828kb
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: 0
Accepted
time: 1ms
memory: 5904kb
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:
2
result:
ok 1 number(s): "2"
Test #4:
score: -100
Wrong Answer
time: 5ms
memory: 5792kb
input:
1000 1000 -468718512 100559444 -466285968 100587272 -463035240 100649294 -461326068 100761398 -459427038 100900610 -455064924 101233256 -452216364 101462348 -450021522 101653544 -449086266 101738960 -433665372 103152428 -429959922 103532498 -427457166 103795826 -418983006 104802926 -416443854 105124...
output:
0 2 2 0 1 2 0 2 1 2 1 0 0 0 0 0 2 1 1 2 0 0 0 2 0 2 2 1 1 1 1 1 1 0 0 1 1 2 1 0 1 1 0 1 1 0 0 1 0 0 1 0 0 0 2 1 2 0 0 0 1 1 2 1 1 0 1 1 2 0 0 0 0 2 1 0 0 0 0 0 1 2 1 2 0 1 0 0 1 0 0 0 0 2 2 1 0 2 1 0 1 1 1 1 0 0 1 0 1 1 2 1 1 2 1 2 2 0 2 2 0 0 0 2 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 1 0 0 0 2 1 ...
result:
wrong answer 1st numbers differ - expected: '1', found: '0'