QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#299900 | #7904. Rainbow Subarray | ucup-team870# | WA | 0ms | 3708kb | C++14 | 2.6kb | 2024-01-07 13:25:09 | 2024-01-07 13:25:10 |
Judging History
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'