QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#299900#7904. Rainbow Subarrayucup-team870#WA 0ms3708kbC++142.6kb2024-01-07 13:25:092024-01-07 13:25:10

Judging History

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

  • [2024-06-09 00:00:26]
  • hack成功,自动添加数据
  • (/hack/652)
  • [2024-01-07 13:25:10]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3708kb
  • [2024-01-07 13:25:09]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;
typedef long long ll;
#define convex vector<P>
const int N=2005,V=1e7;
struct P{
    ll x,y;
    ll len(){return x*x+y*y;}
    bool up(){
        return y>0 || (y>0 && x>=0);
    }
    // bool operator 
}pts[N],q[N];
P operator +(const P&a, const P& b){ return {a.x+b.x,a.y+b.y}; }
P operator -(const P&a, const P& b){ return {a.x-b.x,a.y-b.y}; }
ll operator ^(const P&a, const P& b){ return a.x*b.y-a.y*b.x; }
bool cmp(P a,P b){
    if(a.up() ^ b.up())return a.up()>b.up();
    return (a^b)<0;
}
unordered_map<ll,int>mp;
ll hh(ll x,ll y){return x*V+y;}
convex get_convex(convex a){
    int n=a.size();
    auto cmp1=[&](const P&a,const P&b){
        if(a.y!=b.y)return a.y<b.y;
        return a.x<b.x;
    };
    sort(a.begin(),a.end(),cmp1);
    auto a0=a[0];
    for(auto &v:a)v=v-a0;
    auto cmp2=[&](P &b,P &c){
        if((b^c)!=0)return (b^c)>0;
        return b.len()<c.len();
    };
    sort(a.begin()+1,a.end(),cmp2);
    for(auto &v:a)v=v+a0;
    vector<int>st(n+1);
    int top=0; st[++top]=0;
    rep(i,1,n-1){
        while(top>1 && ((a[i]-a[st[top-1]])^(a[st[top]]-a[st[top-1]]))>=0)--top;
        st[++top]=i;
    }
    vector<P>res; rep(i,1,top)res.push_back(a[st[i]]);
    return res;
}
int ok[N],id[N],ps[N];
int main() {
    IOS
    int n; cin>>n; 
    convex vec;
    rep(i,1,n){
        ll x,y; cin>>x>>y; pts[i]={x,y}; mp[hh(x,y)]=i; vec.push_back(pts[i]);
    }
    convex tb=get_convex(vec);
    for(auto [x,y]:tb)cout<<x<<" tb "<<y<<endl;
    int m=tb.size();
    rep(i,0,m-1){
        auto [x,y]=tb[i];
        int idx=mp[hh(x,y)];
        id[idx]=i; ok[idx]=1;
    }
    auto ck=[&](int x,int y){
        if(!ok[x] || !ok[y])return false;
        x=id[x]; y=id[y];
        return (y-(x+1))%m==0 || (x-(y+1))%m==0;
    };
    int ans=0;
    rep(i,1,n){
        if(ok[i])continue;
        int cnt=0;
        rep(j,1,n){
            if(j==i)continue;
            q[++cnt]=pts[j];
        }
        sort(q+1,q+cnt+1,cmp);
        rep(j,1,cnt){
            auto [x,y]=q[j]; ps[j]=mp[hh(x,y)];
        }
        ps[cnt+1]=ps[1];
        rep(j,1,cnt){
            if(ck(ps[j],ps[j+1])){
                ++ans;
                cout<<i<<" "<<ps[j]<<" "<<ps[j+1]<<endl;
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}
/*
7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

0 tb 0
4 tb 0
3 tb 5
1 tb 4
3 2 6
3 6 1
4 2 6
4 6 1
7 1 5
7 2 6
7 6 1
7
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
7 5
7 2 5 5 4 11 7
6 0
100 3 4 5 99 100
5 6
1 1 1 1 1
5 50
100 200 300 400 500
1 100
3

output:

7 tb 2
7 tb 6
4 tb 11
5 tb 5
1 4 3
1 5 2
2

result:

wrong answer 1st lines differ - expected: '4', found: '7 tb 2'