QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#566159#8468. Collinear Arrangementsucup-team1231#WA 151ms5992kbC++233.4kb2024-09-15 23:11:062024-09-15 23:11:06

Judging History

你现在查看的是最新测评结果

  • [2024-09-15 23:11:06]
  • 评测
  • 测评结果:WA
  • 用时:151ms
  • 内存:5992kb
  • [2024-09-15 23:11:06]
  • 提交

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
*/

Details

Tip: Click on the bar to expand more detailed information

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'