QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#566159 | #8468. Collinear Arrangements | ucup-team1231# | WA | 151ms | 5992kb | C++23 | 3.4kb | 2024-09-15 23:11:06 | 2024-09-15 23:11:06 |
Judging History
answer
#pragma GCC optimize("Ofast","unroll-all-loops","fast-math")
#include <bits/stdc++.h>
using namespace std;
#define SZ 200999
typedef pair<int,int> pii;
#define sz(u) (int((u).size()))
#define x first
#define fi first
#define se second
#define y second
typedef double ld;
typedef long long ll;
struct Line {
mutable ll k,m; mutable ld p; int u;
bool operator < (const Line&o) const {return k<o.k;}
bool operator < (ld s) const {return p<s;}
};
struct LC: multiset<Line,less<>> {
static constexpr ld inf=1e2333;
bool isect(iterator x,iterator y) {
if(y==end()) return x->p=inf,0;
if(x->k==y->k) x->p=x->m>y->m?inf:-inf;
else x->p=ld(y->m-x->m)/(x->k-y->k);
return x->p>=y->p;
};
void add(ll k,ll m,int i) {
auto z=insert({k,m,0,i}),y=z++,x=y;
while(isect(y,z)) z=erase(z);
if(x!=begin()&&isect(--x,y)) isect(x,y=erase(y));
while((y=x)!=begin()&&(--x)->p>=y->p)
isect(x,erase(y));
}
int query(ld x) {
assert(!empty());
auto l=*lower_bound(x);
return l.u;
}
}A,B;
int n,q; pii s[SZ];
ll h[SZ];
ll easy(pii t) {
unordered_map<ll,int> ss;
ll ans=0;
for(int i=0;i<n;++i) {
pii w(s[i].fi-t.fi,s[i].se-t.se);
ll g=__gcd(w.fi,w.se);
w.fi/=g,w.se/=g;
if(w.fi<0) w.fi*=-1,w.se*=-1;
if(w.se<0) w.fi*=-1,w.se*=-1;
cerr<<w.fi<<","<<w.se<<" ";
h[i]=(w.fi+ll(2.01e9))*ll(4e9)+w.se;
ans+=ss[h[i]]++;
}
cerr<<"\n";
return ans;
}
int main() {
scanf("%d%d",&n,&q);
for(int i=0;i<n;++i)
scanf("%d%d",&s[i].fi,&s[i].se),
A.add(s[i].fi,s[i].se,i),
B.add(-s[i].fi,-s[i].se,i);
int u=min_element(s,s+n)-s,v=max_element(s,s+n)-s;
while(q--) {
int o; pii a,b;
scanf("%d%d%d",&o,&a.fi,&a.se);
if(o==1) {
printf("%lld\n",easy(a));
continue;
}
scanf("%d%d",&b.fi,&b.se);
int MI=-1,MX=-1;
ll mi=8e18,mx=-8e18;
pii S(b.se-a.se,a.fi-b.fi);
auto qry=[&](pii t) {
return S.fi*(ll)t.fi+S.se*(ll)t.se;
};
auto upd=[&](int s) {
s=(s-5)%n; if(s<0) s+=n;
for(int w=0;w<10;++w) {
int v=(s+w)%n;
ll dp=qry(::s[v]);
if(MI==-1||mi>dp) mx=dp, MI=v;
if(MX==-1||mx<dp) mx=dp, MX=v;
}
};
upd(u); upd(v);
upd(A.query(ld(S.fi)/S.se));
upd(B.query(ld(S.fi)/S.se));
ll FD = qry(a);
unordered_set<int> ans;
// find where it >= FD
{
int L=MX,R=MI;
if(L>R) R+=n;
while(L<R) {
int M=(L+R+1)>>1;
if(qry(::s[M%n])>=FD) L=M;
else R=M-1;
}
for(int s=L-3;s<=L+3;++s) {
int p=(s%n+n)%n;
if(qry(::s[p])==FD) ans.insert(p);
}
}
{
int L=MI,R=MX;
if(L>R) R+=n;
while(L<R) {
int M=(L+R+1)>>1;
if(qry(::s[M%n])<=FD) L=M;
else R=M-1;
}
for(int s=L-3;s<=L+3;++s) {
int p=(s%n+n)%n;
if(qry(::s[p])==FD) ans.insert(p);
}
}
printf("%d\n",int(ans.size()));
}
}
/*
5 3
0 0
2 0
2 1
1 2
0 2
2 1 1 2 2
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5872kb
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: 3820kb
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: 0ms
memory: 3908kb
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: 151ms
memory: 5992kb
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:
1 0 0 1 1 2 1 2 1 2 1 1 1 0 0 1 2 1 1 2 0 0 0 2 0 2 0 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 0 1 0 0 1 1 0 1 1 0 1 1 0 0 1 0 0 2 1 0 1 0 0 0 1 0 1 2 0 1 0 0 1 1 0 0 0 0 2 1 0 0 1 0 1 1 1 1 1 0 1 1 1 1 0 1 1 2 1 0 2 0 0 0 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 2nd numbers differ - expected: '2', found: '0'