QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#453826#8814. Almost Convex 2triple_dogsWA 0ms7716kbC++143.7kb2024-06-24 12:28:402024-06-24 12:28:41

Judging History

This is the latest submission verdict.

  • [2024-06-24 12:28:41]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 7716kb
  • [2024-06-24 12:28:40]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef bitset<500> bs;
int n;
struct pi{
    int x,y;
    pi operator-(const pi &u){return (pi){x-u.x,y-u.y};}
    int operator^(const pi &u){return x*u.y-y*u.x;}
}a[505];
bool cmp(pi u,pi v){
    if (u.x!=v.x) return u.x<v.x;
    return u.y<v.y;
}
bool eq(pi u,pi v){
    return u.x==v.x&&u.y==v.y;
}
bs f[505][505],g[505];
short cnt[505][505][505];
bool crossop(pi u,pi v,pi w){
    return ((u-w)^(v-w))<0;
}
void print(bs &a){
    for (int i=0;i<n;i++) cout << a[i]; cout << endl;
}
int c[505],id[505];
bool in(int u,int x,int y,int z){
    return f[x][z][u]&&f[z][y][u]&&f[y][x][u];
}
int C2(int x){return x*(x+1)/2;}
int main(){
    cin >> n;
    for (int i=0;i<n;i++) cin >> a[i].x >> a[i].y;
    sort(a,a+n,cmp);
    vector<pi> qs(n*2); int k=0;
    for (int i=0;i<n;qs[k++]=a[i++]){
        while (k>1&&crossop(qs[k-2],qs[k-1],a[i])) --k;
    }
    for (int i=n-2,t=k;i>=0;qs[k++]=a[i--]){
        while (k>t&&crossop(qs[k-2],qs[k-1],a[i])) --k;
    }
    qs.resize(k-1);
    int m=qs.size();
    memset(id,-1,sizeof(id));
    for (int i=0;i<m;i++){
        for (int j=0;j<n;j++) if (eq(qs[i],a[j])){
            c[i]=j;
            id[j]=i;
        }
    }
    c[m]=c[0];
    for (int i=0;i<n;i++)
        for (int j=i+1;j<n;j++) 
            for (int k=j+1;k<n;k++){
                int tmp=(a[i]-a[k])^(a[j]-a[k]);
                if (tmp<0) f[i][j][k]=f[j][k][i]=f[k][i][j]=1;
                else f[i][k][j]=f[k][j][i]=f[j][i][k]=1;
            }
    for (int i=0;i<n;i++)
        for (int j=i+1;j<n;j++)
            for (int k=j+1;k<n;k++){
                int res;
                if (crossop(a[i],a[j],a[k])){
                    res=(f[i][j]&f[j][k]&f[k][i]).count();
                } else {
                    res=(f[i][k]&f[k][j]&f[j][i]).count();
                }
                cnt[i][j][k]=res;
                cnt[i][k][j]=res;
                cnt[j][i][k]=res;
                cnt[j][k][i]=res;
                cnt[k][i][j]=res;
                cnt[k][j][i]=res;
            }
    long long ans=1;
    for (int i=0;i<n;i++) if (id[i]==-1){
        for (int j=0;j<m;j++) if (!cnt[c[j]][c[j+1]][i]){
            g[i][j]=1; ans++;
        }
    }


    for (int i=0;i<n;i++) if (id[i]==-1){
        for (int j=i+1;j<n;j++) if (id[j]==-1){
            //ans+=g[i].count()*g[j].count()-(g[i]&g[j]).count();
            int p=-1,q=-1;
            for (int k=0;k<m;k++){
                if (in(i,c[k],c[k+1],j)) p=k;
                if (in(j,c[k],c[k+1],i)) q=k;
            }
            int lp=0,lq=0,rp=0,rq=0;
            for (int k=(p+1)%m;k!=q;k=(k+1)%m){
                if (g[j][k]) ans+=lp,lq++;
                if (g[i][k]) lp++;
            }
            for (int k=(q+1)%m;k!=p;k=(k+1)%m){
                if (g[i][k]) ans+=rq,rp++;
                if (g[j][k]) rq++;
            }
            if (g[i][k]) ans+=lq+rq;
            if (g[j][k]) ans+=lp+rp;
            if (g[i][k]&&g[j][k]) ans++;
            ans+=lp*rq+lq*rp;
            for (int k=0;k<m;k++){
                if (in(j,c[k],c[k+1],i)){
                    if (g[j][k]){
                        if (!cnt[c[k]][i][j]) ans++;
                        if (!cnt[c[k+1]][i][j]) ans++;
                    }
                } else if (in(i,c[k],c[k+1],j)){
                    if (g[i][k]){
                        if (!cnt[c[k]][i][j]) ans++;
                        if (!cnt[c[k+1]][i][j]) ans++;
                    }
                } else {
                    if (g[i][k]&&g[j][k]&&!cnt[c[k]][i][j]&&!cnt[c[k+1]][i][j]) ans++;
                }
            }
        }
    }
    cout << ans << endl;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 7716kb

input:

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

output:

19

result:

wrong answer 1st numbers differ - expected: '26', found: '19'