QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#626802#7015. Rikka with IlluminationstarjenAC ✓415ms3684kbC++202.1kb2024-10-10 13:08:072024-10-10 13:08:07

Judging History

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

  • [2024-10-10 13:08:07]
  • 评测
  • 测评结果:AC
  • 用时:415ms
  • 内存:3684kb
  • [2024-10-10 13:08:07]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll eps =0;
using pt=ll;
template<typename T> struct point
{
    T x,y;
    bool operator==(const point &a) const {return (abs(x-a.x)<=eps && abs(y-a.y)<=eps);}
    bool operator<(const point &a) const {if(abs(x-a.x)<=eps)return y<a.y-eps;return x<a.x-eps;}
    bool operator>(const point &a) const {return !(*this<a||*this==a);}
    point operator+(const point &a)const {return {x+a.x,y+a.y};}
    point operator-(const point &a)const {return {x-a.x,y-a.y};}
    point operator-()const {return {-x,-y};}
    T operator*(const point &a)const{return x*a.x+y*a.y;}
    T operator^(const point &a)const{return x*a.y-y*a.x;}
    int toleft(const point &a)const{const auto t=(*this)^a;return (t>eps)-(t<-eps);}
};
using Point = point<pt>;
void solve()
{
    int n,m;cin>>n>>m;
    vector<Point> a(n*2);
    for(int i=0;i<n;i++){
        cin>>a[i].x>>a[i].y;
        a[i+n]=a[i];
    }
    vector<Point> b(m);
    for(int i=0;i<m;i++)cin>>b[i].x>>b[i].y;
    vector<pair<int,int>> jump(n*2,make_pair(-1,-1));
    for(int i=0;i<m;i++){
        int pr=-1;
        for(int j=2*n-2;j>=0;j--){
            if((a[j+1]-b[i]).toleft(a[j]-b[i])>0){
                if(pr==-1)pr=j+1;
                // if(j<n)cout<<"edge = "<<j<<" p="<<i<<endl;
            }
            else pr=-1;
            if(pr>jump[j].first){
                jump[j].first=pr;
                jump[j].second=i;
            }
        }
    }
    for(int i=0;i<n;i++)if(jump[i].first==-1){
        cout<<-1<<"\n";return;
    }
    vector<int>ans(m+2);
    for(int i=0;i<n;i++){
        int x=i;
        vector<int>now;
        while(x<i+n){
            now.push_back(jump[x].second);
            x=jump[x].first;
        }
        if(now.size()<ans.size())ans=now;
    }
    cout<<ans.size()<<"\n";
    for(int i=0;i<ans.size();i++)cout<<ans[i]+1<<" \n"[i==ans.size()-1];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--)solve();
}
/*

1
3 3
0 0
1 0
0 1
-1 -1
3 -1
-1 3

1 
3 2
-1 0
1 0
0 1
1 1 
0 -1
*/

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3676kb

input:

1
3 3
0 0
1 0
0 1
-1 -1
3 -1
-1 3

output:

2
2 1

result:

ok 1 cases.

Test #2:

score: 0
Accepted
time: 36ms
memory: 3656kb

input:

100
13 17
-976 -766
-628 -956
462 -987
967 -997
981 -123
919 115
847 336
692 789
350 908
-558 996
-843 944
-944 400
-974 -476
-41876798 919231678
-375313647 26070145
-288061228 527643156
-93144407 730297
93699145 -260606010
-393321698 -339399089
644245933 784344503
-731740672 525632046
-32141854 114...

output:

2
5 1
-1
-1
-1
-1
3
17 19 5
-1
4
13 7 3 5
-1
-1
-1
8
8 15 7 3 14 2 10 11
4
7 6 8 5
-1
3
3 2 7
-1
-1
-1
-1
-1
4
8 2 5 13
4
13 3 12 7
4
5 7 1 2
4
17 48 25 13
4
13 9 38 2
5
37 4 14 6 15
37
88 31 5 40 28 1 59 42 21 17 83 26 76 38 51 7 20 84 4 9 12 14 32 45 24 78 68 73 67 23 29 11 48 49 27 75 34
6
14 5 7...

result:

ok 100 cases.

Test #3:

score: 0
Accepted
time: 373ms
memory: 3636kb

input:

100
1000 1000
-206566811 272513
-206555115 -2214957
-206550642 -2598812
-206538524 -3429227
-206534118 -3685047
-206497885 -5342748
-206466348 -6447384
-206454728 -6809307
-206416737 -7877319
-206365268 -9126757
-206352649 -9407755
-206350222 -9460834
-206342491 -9627970
-206253359 -11378633
-206140...

output:

-1
106
603 640 460 660 850 722 695 573 214 282 375 711 683 421 276 30 107 95 561 191 564 413 506 77 836 186 822 11 515 499 882 42 818 524 789 443 249 140 451 872 525 422 344 969 147 716 227 217 577 46 194 877 452 980 903 281 178 24 803 612 75 1 957 216 416 895 173 254 970 39 812 380 205 653 912 887 ...

result:

ok 100 cases.

Test #4:

score: 0
Accepted
time: 415ms
memory: 3684kb

input:

100
1000 1000
-208687104 -518935
-208658071 -3519412
-208647420 -4102540
-208612602 -5599926
-208458791 -9772885
-208145426 -15035235
-207718591 -20088894
-207636408 -20921257
-207598046 -21298548
-207567860 -21590745
-207181177 -25030716
-206899863 -27258453
-206707452 -28681109
-206631693 -2922191...

output:

461
985 29 304 608 501 941 22 656 91 73 712 725 98 245 609 33 81 970 514 593 559 453 882 880 626 357 452 249 455 993 90 956 9 254 197 731 316 854 37 662 340 539 613 927 787 8 664 874 398 142 998 409 670 270 715 136 746 695 668 96 430 217 403 982 436 407 857 373 42 707 631 105 102 822 831 793 502 529...

result:

ok 100 cases.