QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#453826 | #8814. Almost Convex 2 | triple_dogs | WA | 0ms | 7716kb | C++14 | 3.7kb | 2024-06-24 12:28:40 | 2024-06-24 12:28:41 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'