QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#852394#9882. Two Convex SetsWuyanruWA 407ms121352kbC++144.6kb2025-01-11 11:39:122025-01-11 11:39:20

Judging History

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

  • [2025-01-11 11:39:20]
  • 评测
  • 测评结果:WA
  • 用时:407ms
  • 内存:121352kb
  • [2025-01-11 11:39:12]
  • 提交

answer

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
const int mod=10000007;
const int base=137;
ll B[10];
struct Hash
{
    int head[10000010];
    ll v1[2000010],v2[2000010];
    int nx[2000010];
    int cnt;ll C1,C2;
    inline void ins(ll g,int v)
    {
        if(!v) return ;
        int u=g%mod;
        for(int i=head[u];i;i=nx[i]) if(v1[i]==g)  
        {
            v2[i]+=v;
            return ;
        }
        else C2++;
        cnt++,v1[cnt]=g,v2[cnt]=v;
        nx[cnt]=head[u],head[u]=cnt;
    }
    inline void ins(int a,int b,int c,int d,int e,int f,int v)
    {
        if(!v) return ;
        ll g=0;C1++;
        g=g*base+a;g=g*base+b;g=g*base+c;g=g*base+d;g=g*base+e;g=g*base+f;
        ins(g,v);
    }
    inline void clear()
    {
        cnt=C1=C2=0;
        memset(head,0,sizeof(head));
    }
}tp[2];
ll dp[2][45][45],fp[2][45][45];
struct node{ ld x,y;}a[45];
int n;
inline bool check(int x,int y,int z)
{
    if(!x||!z) return true;
    ld x1=a[y].x-a[x].x,y1=a[y].y-a[x].y;
    ld x2=a[z].x-a[y].x,y2=a[z].y-a[y].y;
    return x1*y2-x2*y1>=0;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();
    sort(a+1,a+n+1,[](node a,node b)
    {
        if(a.y!=b.y) return a.y<b.y;
        return a.x<b.x;
    });
    sort(a+2,a+n+1,[](node b,node c)
    {
        ld x1=b.x-a[1].x,y1=b.y-a[1].y,z1=sqrtl(x1*x1+y1*y1);
        ld x2=c.x-a[1].x,y2=c.y-a[1].y,z2=sqrtl(x2*x2+y2*y2);
        return x1/z1>x2/z2;
    });
    B[0]=1;
    for(int i=1;i<=5;i++) B[i]=B[i-1]*base;
    int now=0,lst=1;dp[now][1][0]=1;

    for(int i=2;i<=n;i++)
    {
        //加入点 i
        swap(now,lst);
        memset(dp[now],0,sizeof(dp[now]));
        memset(fp[now],0,sizeof(fp[now]));
        tp[now].clear();

        for(int x=0;x<=i;x++) for(int y=0;y<=i;y++)
        {
            //dp[x][y] and fp[x][y]
            if(check(y,x,i))
            {
                dp[now][i][x]+=dp[lst][x][y];
                fp[now][i][x]+=fp[lst][x][y];
            }
            fp[now][x][y]+=dp[lst][x][y];
            tp[now].ins(x,y,i,0,i,0,dp[lst][x][y]);
        }
        for(int j=1;j<=tp[lst].cnt;j++)
        {
            ll v=tp[lst].v2[j],id=tp[lst].v1[j],g=id;
            int a,b,c,d,e,f;
            f=g%base,g/=base;e=g%base,g/=base;d=g%base,g/=base;
            c=g%base,g/=base;b=g%base,g/=base;a=g%base,g/=base;

            bool f1=0,f2=0;
            if(check(b,a,i)) tp[now].ins(i,a,c,d,e,f,v);
            if(check(d,c,i)) tp[now].ins(a,b,i,c,e,f?f:i,v),f1=1;
            if(check(i,e,f)) tp[now].ins(a,b,c,d?d:i,i,e,v),f2=1;
            if(f1&&f2)
            {
                fp[now][a][b]+=v;
                // printf("(%d,%lld)%d %d %d %d %d %d + %d v=%lld -> fp %d %d\n",j,tp[lst].v1[j],a,b,c,d,e,f,i,v,a,b);
            }
        }

        // ll ans=0;
        // for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) if(check(j,i,1)) ans+=dp[now][i][j]+fp[now][i][j];
        // printf("i=%d : %Lf %Lf %d  (%lld,%lld) %lld\n",i,a[i].x,a[i].y,tp[now].cnt,tp[now].C1,tp[now].C2,ans);

        // for(int x=0;x<=n;x++) for(int y=0;y<=n;y++) if(dp[now][x][y]) printf("dp[%d][%d]=%lld\n",x,y,dp[now][x][y]);
        // for(int x=0;x<=n;x++) for(int y=0;y<=n;y++) if(fp[now][x][y]) printf("fp[%d][%d]=%lld\n",x,y,fp[now][x][y]);
        // for(int j=1;j<=tp[now].cnt;j++)
        // {
        //     ll v=tp[now].v2[j],g=tp[now].v1[j];
        //     int a,b,c,d,e,f;
        //     f=g%base,g/=base;e=g%base,g/=base;d=g%base,g/=base;
        //     c=g%base,g/=base;b=g%base,g/=base;a=g%base,g/=base;
        //     printf("tp %d %d %d %d %d %d : %lld\n",a,b,c,d,e,f,v);
        // }
    }
    ll ans=0;
    for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) if(check(j,i,1))
    {
        ans+=dp[now][i][j]+fp[now][i][j];
        // if(dp[now][i][j]) printf("ans dp[%d][%d]=%lld\n",i,j,dp[now][i][j]);
        // if(fp[now][i][j]) printf("ans fp[%d][%d]=%lld\n",i,j,fp[now][i][j]);
    }
    printf("%lld\n",ans*2);
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 93980kb

input:

4
0 0
3 0
0 3
1 1

output:

14

result:

ok "14"

Test #2:

score: 0
Accepted
time: 15ms
memory: 93140kb

input:

8
1 0
2 0
3 1
3 2
2 3
1 3
0 2
0 1

output:

256

result:

ok "256"

Test #3:

score: 0
Accepted
time: 23ms
memory: 93816kb

input:

10
0 0
1 1
7 1
1 7
3 2
2 3
4 2
2 4
5 4
4 5

output:

0

result:

ok "0"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

1
0 0

output:

2

result:

ok "2"

Test #5:

score: 0
Accepted
time: 3ms
memory: 48960kb

input:

2
1000000 0
0 1000000

output:

4

result:

ok "4"

Test #6:

score: 0
Accepted
time: 109ms
memory: 92856kb

input:

40
675677 -903121
254211 732097
792262 -321884
701349 560077
430182 -715346
404091 -587385
-368483 765887
-62363 -93377
964720 739688
-63560 -743279
-445506 491429
758128 486841
571801 -759073
-838475 443367
238435 -29645
651624 -991716
-747006 397530
-616854 -868231
656953 925190
-317709 453131
-16...

output:

0

result:

ok "0"

Test #7:

score: 0
Accepted
time: 105ms
memory: 93996kb

input:

40
-865418 42040
-181476 58360
-864436 597211
-537311 -750515
653760 930646
-79954 431109
507863 569812
-756842 328289
-847028 -653883
-861260 953897
172940 -670358
-897079 -318722
-322040 580667
-110419 -862581
-673197 497171
160617 197820
-685798 -274098
-996233 -444341
-866456 -103514
884216 1302...

output:

0

result:

ok "0"

Test #8:

score: 0
Accepted
time: 129ms
memory: 93096kb

input:

40
-603027 -206745
522738 -843934
-230260 171562
409437 -780802
335077 938627
900036 446118
353133 613669
42034 -253742
897735 244447
162857 -205668
-291578 255993
-400956 -443041
363918 -151931
917921 -153303
-784264 -923508
707263 -65982
320014 -741462
69068 84317
-313477 -222217
398310 -623897
-3...

output:

0

result:

ok "0"

Test #9:

score: -100
Wrong Answer
time: 407ms
memory: 121352kb

input:

40
304228 474832
339193 698218
532597 847991
301767 487867
301484 489588
312216 636492
301156 589241
864900 341382
815916 788658
902793 401404
383829 322243
311538 634321
934723 542442
934711 543872
849568 323602
317879 652850
297933 558903
545644 229664
426994 283936
932543 577716
803173 282502
612...

output:

996432412672

result:

wrong answer 1st words differ - expected: '1099511627776', found: '996432412672'