QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#685828 | #8814. Almost Convex 2 | Crysfly | TL | 988ms | 4880kb | C++14 | 5.3kb | 2024-10-28 21:29:46 | 2024-10-28 21:29:47 |
Judging History
answer
// what is matter? never mind.
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
//#define int long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
typedef double db;
const db eps=1e-8,pi=3.14159265358979323846;
int sgn(int x){return x<0?-1:x>0;}
int cmp(int a,int b){return sgn(a-b);}
struct P{
int x,y,id;
P(int x=0,int y=0):x(x),y(y){}
P&operator +=(P o){return x+=o.x,y+=o.y,*this;}
P&operator -=(P o){return x-=o.x,y-=o.y,*this;}
P&operator *=(int o){return x*=o,y*=o,*this;}
P&operator /=(int o){return x/=o,y/=o,*this;}
friend P operator +(P a,P b){return a+=b;}
friend P operator -(P a,P b){return a-=b;}
friend P operator *(P a,int b){return a*=b;}
friend P operator /(P a,int b){return a/=b;}
friend bool operator <(P a,P b){return fabs(a.x-b.x)<eps?a.y<b.y:a.x<b.x;}
friend bool operator ==(P a,P b){return cmp(a.x,b.x)==0 && cmp(a.y,b.y)==0;}
friend bool operator !=(P a,P b){return !(a==b);}
friend int operator %(P a,P b){return a.x*b.x+a.y*b.y;} // dot
friend int operator *(P a,P b){return a.x*b.y-a.y*b.x;} // cross
P rot90(){return P(-y,x);}
db ang(){return atan2(y,x);}
db len(){return sqrt(x*x+y*y);}
int len2(){return x*x+y*y;}
int half(){return sgn(y)==1||(sgn(y)==0&&sgn(x)>=0);}
// P unit(){return ((*this))/len();}
void read(){cin>>x>>y;}
void out(){cout<<"("<<x<<","<<y<<")"<<endl;}
};
bool cmp_dir(P a,P b){
if(a.half()!=b.half())return a.half()<b.half();
return sgn(a*b)>0;
}
db dis(P a,P b){return (a-b).len();}
int cross(P a,P b,P c){
// (a->b)*(a->c)
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int cmp3(P a,P b,P c){
return sgn(cross(a,b,c));
}
vector<P>convex(vector<P>a){
int n=a.size(),m=0; if(n<=1)return a;
sort(a.begin(),a.end());
vector<P>st(n*2); int tp=0;
For(i,0,n-1){
while(tp>1 && cmp3(st[tp-2],st[tp-1],a[i])<=0)--tp;
st[tp++]=a[i];
}
int t=tp;
Rep(i,n-2,0){
while(tp>t && cmp3(st[tp-2],st[tp-1],a[i])<=0)--tp;
st[tp++]=a[i];
}
st.resize(tp-1);
return st;
}
bool in_tri(P a,P b,P c,P p){
if(cmp3(a,b,c)<0) swap(b,c);
return cmp3(a,b,p)>=0 && cmp3(b,c,p)>=0 && cmp3(c,a,p)>=0;
}
#define maxn 505
#define inf 0x3f3f3f3f
int n,m1,m2;
P p[maxn];
vector<P>h,in;
bool vis[maxn];
int cnt[maxn][maxn];
bool chk(int i,int j,int k){
For(x,1,n) if(x!=i&&x!=j&&x!=k && in_tri(p[i],p[j],p[k],p[x])) return 1;
return 0;
return cnt[i][j]+cnt[j][k]+cnt[k][i]!=0;
}
ll res;
bool hav[maxn][maxn];
bool col[maxn];
int sum[maxn];
bool isseg_s(P p1,P p2,P q1,P q2){
return cmp3(p1,p2,q1)*cmp3(p1,p2,q2)<0 && cmp3(q1,q2,p1)*cmp3(q1,q2,p2)<0;
}
signed main()
{
n=read();
For(i,1,n) p[i].x=read(),p[i].y=read();
sort(p+1,p+n+1);
For(i,1,n) p[i].id=i,h.pb(p[i]);
h=convex(h);
for(auto it:h) vis[it.id]=1;
For(i,1,n) if(!vis[i]) in.pb(p[i]);
For(i,2,n) For(j,i+1,n) {
For(k,2,n) if(k!=i && k!=j) cnt[i][j]+=in_tri(p[1],p[i],p[j],p[k]);
cnt[j][i]=cnt[i][j];
if(cmp3(1,i,j)>0) cnt[j][i]=-cnt[j][i];
else cnt[i][j]=-cnt[i][j];
}
m1=h.size();
m2=in.size();
res=1;
For(i,0,m1-1){
For(j,0,m2-1){
hav[i][j]=chk(h[i].id,h[(i+1)%m1].id,in[j].id);
if(!hav[i][j]) ++res;
}
}
// cout<<"cut1 "<<res<<"\n";
// cout<<"sz "<<m1<<" "<<m2<<"\n";
int now2=0;
For(i,0,m1-1){
For(j,0,m2-1) if(!hav[i][j]) {
int u=h[i].id,v=h[(i+1)%m1].id,w=in[j].id;
For(k,0,m2-1) if(j!=k) {
// if((!chk(u,w,in[k].id))) cout<<"add "<<u<<" "<<w<<" "<<in[k].id<<"\n";
// if((!chk(v,w,in[k].id))) cout<<"add "<<v<<" "<<w<<" "<<in[k].id<<"\n";
for(auto x:{u,v}){
if(!chk(x,w,in[k].id) && !isseg_s(p[x^u^v],p[w],p[x],in[k])){
++res;
if(!in_tri(p[u],p[v],in[k],p[w])) ++now2;//cout<<"Add2 "<<u<<" "<<v<<" "<<in[k].id<<" "<<w<<"\n";
}
}
}
}
}
// cout<<"now2 "<<now2<<"\n";
res-=now2/2;
// cout<<"cut2 "<<res<<"\n";
For(i,0,m1-1){
sum[i]=0;
For(j,0,m2-1) if(!hav[i][j]) ++sum[i];
res+=sum[i]*(sum[i]-1)/2;
}
For(i,0,m1-1) For(j,i+1,m1-1) res+=sum[i]*sum[j];
// cout<<"res "<<res<<"\n";
For(i,0,m2-1){
int ss=0;
For(j,0,m1-1) if(!hav[j][i]) ++ss;
res-=ss*(ss-1)/2;
}
For(i,0,m2-1)
For(j,0,m2-1) if(i!=j) {
int now=0;
For(k,0,m1-1) {
col[k]=cmp3(in[i],in[j],h[k])>0;
}
For(k,0,m1-1){
if(col[k]==1) now+=(!hav[k][j]);
}
// cout<<"i,j "<<i<<" "<<j<<"\n";
// For(k,0,m1-1) cout<<col[k]<<" "; cout<<" col\n";
For(k,0,m1-1) if(col[k] && !col[(k+m1-1)%m1]) {
while(col[k]) {
if(!hav[k][i]) res-=now;//cout<<"sub "<<k<<" "<<now<<"\n";
now-=(!hav[k][j]);
k=(k+1)%m1;
}
break;
}
}
cout<<res;
return 0;
}
/*
9
0 2
1 0
1 3
2 1
2 5
3 0
3 3
4 2
5 5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3524kb
input:
7 0 2 1 0 1 3 2 5 3 0 3 3 4 2
output:
26
result:
ok 1 number(s): "26"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
5 4 0 0 0 2 1 3 3 3 1
output:
13
result:
ok 1 number(s): "13"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
6 0 0 3 0 3 2 0 2 1 1 2 1
output:
20
result:
ok 1 number(s): "20"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 643ms
memory: 4820kb
input:
500 -5276 -1176 3417 -883 -6586 -1581 4425 7450 -7896 -3039 -6316 2357 5464 2109 -3428 -6184 -1477 -1383 -5288 -969 -5528 -4316 -508 -364 -7424 -4848 -1073 -9882 4320 -862 -4720 -2569 560 -5594 -4492 -7290 3629 9120 3112 5970 -2587 -4693 7147 -6919 -935 8748 2664 4405 -6865 -3149 8844 -4641 -3706 -9...
output:
50930
result:
ok 1 number(s): "50930"
Test #7:
score: 0
Accepted
time: 502ms
memory: 4872kb
input:
500 8598 4438 6327 -913 -4037 -1025 7337 -4117 -3092 1011 378 -7033 -8724 4431 -4868 5150 911 529 5509 -1362 1086 -7919 9778 1261 -3832 3610 -3470 7906 -8559 5595 -8075 2232 -4577 -9072 -4482 -6029 8463 -1196 7884 -316 -9376 1920 6846 -8409 2715 -7335 -4977 -4130 9147 1621 -8337 1592 4062 -6829 208 ...
output:
16737
result:
ok 1 number(s): "16737"
Test #8:
score: 0
Accepted
time: 850ms
memory: 4692kb
input:
500 9007 265 2201 5042 5284 -119 5263 2146 9479 -2911 -6239 -4536 2430 978 5311 9052 3692 -754 -2856 -7654 3911 -2955 -4557 6411 -8410 5578 -1429 -8277 -4974 -6226 7160 -2990 -1285 7944 -7144 -6104 -632 -5051 -5904 -3302 -2994 6223 -4918 -773 -2706 -5848 8741 4050 -4544 -3399 -3329 5833 9436 6073 91...
output:
78511
result:
ok 1 number(s): "78511"
Test #9:
score: 0
Accepted
time: 528ms
memory: 4640kb
input:
500 3986 -2058 8393 -5560 -9323 -8268 -7531 8178 -8691 8818 -9752 -1098 8298 -9389 5224 -3089 -5027 2759 -7845 -4577 -7195 6292 8610 4357 -3948 9888 -6300 8917 -7351 2477 1514 -7484 -8936 -5060 -9687 -2927 4009 1765 7666 -4956 1790 -8694 6446 2739 6425 3415 4940 -7749 -2186 1776 3011 -1438 7967 -330...
output:
16065
result:
ok 1 number(s): "16065"
Test #10:
score: 0
Accepted
time: 631ms
memory: 4584kb
input:
500 -374 -6853 8340 3978 2984 9235 7388 7881 9251 -114 9415 -4001 -4986 -9491 4528 -6929 -6788 -3585 4280 -9908 -762 242 2141 -6162 -6597 -1198 -7204 -9704 9557 3683 -2219 -2905 5487 -254 8407 -9416 -2740 -3414 4907 -7751 2333 -1087 -7493 -989 1742 4989 2200 -5320 2136 5551 8421 -4805 -2601 3272 332...
output:
44326
result:
ok 1 number(s): "44326"
Test #11:
score: 0
Accepted
time: 472ms
memory: 4532kb
input:
500 593 4401 -8062 3551 1693 -5367 1067 3359 9605 3156 -406 9613 7086 -4924 -604 -6096 -8304 4829 3056 108 -1251 -8599 -6915 -9995 -1362 -9650 -2693 3354 7446 -7474 -8427 8752 2577 9247 -7860 -8455 -4310 8633 3811 2165 6056 -1335 2385 1666 6845 5528 1344 -7649 9146 8372 -7986 -9293 6077 -4673 1922 4...
output:
6406
result:
ok 1 number(s): "6406"
Test #12:
score: 0
Accepted
time: 357ms
memory: 4616kb
input:
500 3099 -3613 -1110 -8776 -931 -8597 1801 -5174 1445 -5583 7743 2043 1472 -5625 6639 694 -376 -7771 4728 -1624 410 -6958 1388 -5725 -149 -7532 4549 -1874 -4 -7433 2847 -3912 891 -6365 590 -6606 1967 -5042 841 -6287 6004 -57 1223 -5935 -833 -8406 -245 -7679 2117 -4778 7743 2032 1729 -5281 5351 -903 ...
output:
197
result:
ok 1 number(s): "197"
Test #13:
score: 0
Accepted
time: 372ms
memory: 4872kb
input:
500 3885 -2913 1167 -5191 73 -8538 2621 -6999 2629 -4437 4959 -465 5623 1751 2643 -1832 1572 -5699 5553 1666 -356 -7904 4749 1822 2349 -6442 3379 -3102 1872 -5412 4961 662 2083 -5685 2096 -6485 4689 -3385 -152 -8592 4433 -1322 3523 -514 4347 580 2503 -4166 -1955 -9807 5591 2896 1192 -6199 5292 160 1...
output:
451
result:
ok 1 number(s): "451"
Test #14:
score: 0
Accepted
time: 376ms
memory: 4872kb
input:
500 4703 -3537 1504 -3821 -6015 649 4331 -4832 -2506 -5255 -6347 -3940 -4134 -3950 -5031 -323 -1641 617 -6416 -5181 -2286 -1047 -3477 -273 1775 -687 -813 -4349 -3080 -5598 -6060 901 4932 -4387 -4701 -5113 -1337 -838 5338 -2177 -5528 1270 2423 -1917 6564 -4480 -3694 851 -5534 -2471 -7040 -1041 -4287 ...
output:
730
result:
ok 1 number(s): "730"
Test #15:
score: 0
Accepted
time: 428ms
memory: 4880kb
input:
500 7026 -796 4816 4861 1394 -296 3528 2969 -7882 1392 -2804 86 -8313 1917 -3064 2479 -247 328 5800 -2136 -1094 -1286 1714 4399 8420 45 -9768 2140 -4357 3676 4346 513 763 -1562 1316 -123 5566 -2472 5627 1144 4377 -2051 1573 -162 -663 2326 2110 -2341 -2981 1763 2642 4347 8728 -232 -250 212 109 3528 -...
output:
1726
result:
ok 1 number(s): "1726"
Test #16:
score: 0
Accepted
time: 395ms
memory: 4644kb
input:
500 1086 -1637 -3054 -5073 3413 -1260 2652 8263 4541 7480 6877 -2262 6482 -1053 4566 -7032 6441 -1846 -4005 5395 5054 294 1954 -3228 -3558 -7090 -733 3598 -2688 9631 -5591 6213 4930 133 -6289 700 -1281 2957 -1931 -1860 -5175 -215 4871 480 5815 1130 2616 7270 -4469 6242 -1606 -4570 -1527 -1512 714 -5...
output:
1636
result:
ok 1 number(s): "1636"
Test #17:
score: 0
Accepted
time: 399ms
memory: 4576kb
input:
500 -4098 -5374 -273 -4345 -7714 -2543 -402 1781 1181 5600 -649 3470 -1834 -4783 -2827 2132 -3728 7158 -3292 5244 -7017 2471 -4170 -217 -4474 2150 -5548 1110 -5063 622 -5113 -6841 -1441 6356 -788 -8869 -3838 -6330 -4971 -6124 -7171 -2830 -7899 3421 -6812 5019 -2875 -8133 -3935 -6568 -1384 -4839 -463...
output:
1933
result:
ok 1 number(s): "1933"
Test #18:
score: 0
Accepted
time: 539ms
memory: 4648kb
input:
500 5829 -5559 1076 5350 1990 -4981 -2819 -1092 -4399 5522 8764 1647 4772 2032 3146 1776 8143 2299 -223 5894 2371 2677 2740 3811 -3681 6540 -4825 4497 1978 -3706 -2779 740 2883 4579 -4622 5659 7763 -1843 6219 467 5671 6080 191 2107 2030 2805 3747 -2114 1349 -5959 3881 4128 -2357 7747 5407 246 7058 8...
output:
10400
result:
ok 1 number(s): "10400"
Test #19:
score: 0
Accepted
time: 435ms
memory: 4648kb
input:
500 -5173 -1176 -4789 -5208 2087 -1307 2704 -3725 7437 319 -2616 5262 6845 -3304 5133 6452 3848 -5212 -7629 1435 1479 8120 -4794 4679 5907 3805 -6280 4522 8428 2486 -503 -1004 2162 -1654 -3573 -5852 4746 6698 2899 -118 4079 -5989 5219 6150 7610 1938 -7783 6278 -5038 2860 -4036 -3160 3276 -2885 109 -...
output:
10280
result:
ok 1 number(s): "10280"
Test #20:
score: 0
Accepted
time: 988ms
memory: 4620kb
input:
500 8 -5246 694 8347 4118 3545 6792 1200 -3866 -6495 -8630 5051 -6449 -5279 2467 1866 1528 3393 -8591 -1037 1442 3832 5564 -3687 3308 1896 -3160 2854 4810 5992 -2438 3712 4084 5843 2705 -7533 7966 602 1665 3345 3186 6666 -7663 3140 4927 4851 -6383 4284 2883 291 -1034 4380 -182 5228 -5679 -4017 985 2...
output:
427502
result:
ok 1 number(s): "427502"
Test #21:
score: -100
Time Limit Exceeded
input:
500 5790 6369 1448 -2220 -2691 -2098 8076 -1871 -7502 -6611 -286 -634 -5341 8453 -2105 -7513 4099 -4617 3598 -9330 5146 -602 3656 4636 6972 -1194 -5992 2205 -2894 -54 415 -3218 -3409 -36 1710 -6872 -1794 4844 -6866 -3165 -8430 326 7198 4957 2300 -2335 -7551 -4571 -4848 5341 8967 -396 960 7519 -7936 ...