QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#455013 | #7906. Almost Convex | sunkaihuan | RE | 0ms | 3884kb | C++14 | 8.0kb | 2024-06-25 17:40:04 | 2024-06-25 17:40:04 |
Judging History
answer
#include<bits/stdc++.h>
#define ld double
#define PI 3.14159265358
using namespace std;
const ld eps=1e-8;
ld sqr(ld x){return x*x;}
int sgn(ld x){return x>eps?1:(x<-eps?-1:0);}
struct point{
ld x,y;int c;
point(ld X=0,ld Y=0){x=X,y=Y;}
point operator+(const point&a)const{return {x+a.x,y+a.y};}
point operator-(const point&a)const{return {x-a.x,y-a.y};}
point operator*(const ld a)const{return {x*a,y*a};}
point operator/(const ld a)const{
if(!a){/*//cerr<<"point div 0";*/return {0,0};}
return {x/a,y/a};}
bool operator==(const point&a)const{
return !sgn(x-a.x)&&!sgn(y-a.y);}
bool operator<(const point&a)const{
return x<a.x||x==a.x&&y<a.y;}
point rotate(ld t)const{
/*绕原点逆时针旋转 t*/
return {x*cos(t)-y*sin(t),x*sin(t)-y*cos(t)};}
point rot90()const{
/*绕原点逆时针旋转 90 度*/
return {-y,x};}
point unit()const{
/*作为自由向量与单位圆交点*/
return *this/sqrt(sqr(x)+sqr(y));}
}O;
ld dis(const point&a,const point&b){
return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
struct line{
point s,t;
line(point S=point(0,0),point T=point(0,0)){s=S,t=T;}
};
ld dot(const point&a,const point&b){
/*点积*/
return a.x*b.x+a.y*b.y;}
ld det(const point&a,const point&b){
/*叉积,张成的平行四边形面积*/
return a.x*b.y-b.x*a.y;}
bool turn_left(const point&a,const point&b,const point&c){
/*AB 逆时针旋转至 AC 时,转角是否在 (0,pi) 区间内*/
return sgn(det(b-a,c-a))>0;}
bool parallel(const line&a,const line&b){
/*向量 a,b 是否平行*/
return !sgn(det(b.t-b.s,a.t-a.s));}
bool same_dir(const line&a,const line&b){
/*向量 a,b 是否同向*/
return parallel(a,b)&&sgn(dot(b.t-b.s,a.t-a.s))>0;}
bool point_on_line(const point&a,const line&l){
/*点 a 是否在线段 l 上*/
if(l.s==l.t)return a==l.s;
return (sgn(det(l.s-a,a-l.t))==0);}
bool point_on_segment(const point&a,const line&l){
/*点 a 是否在线段 l 上*/
return point_on_line(a,l)&&(sgn(dot(l.s-a,a-l.t))>=0);}
bool two_side(const point&a,const point&b,const line&l){
/*点 a,b 是否分别在 l 两侧*/
return sgn(det(a-l.s,l.t-l.s))*sgn(det(b-l.s,l.t-l.s))<0;}
bool inter_judge(const line&a,const line&b){
/*线段 a,b 是否相交*/
return point_on_segment(b.s,a)||point_on_segment(b.t,a)||
point_on_segment(a.s,b)||point_on_segment(a.t,b)||
two_side(a.s,a.t,b)&&two_side(b.s,b.t,a);}
point line_intersect(const line&a,const line&b){
/*求直线 a,b 的交点*/
ld u=det(a.t-a.s,b.s-a.s),v=-det(a.t-a.s,b.t-a.s);
return (b.s*v+b.t*u)/(v+u);}
bool ray_inter_judge(const line&a,const line&b){
/*射线 a,b 是否相交*/
if(parallel(a,b))return 0;
point p=line_intersect(a,b);line c={a.s,p},d={d.s,p};
return(point_on_segment(p,a)||point_on_segment(a.t,c))&&
(point_on_segment(p,b)||point_on_segment(b.t,d));}
ld point_to_line(const point&p,const line&l){
/*点 p 到直线 l 距离*/
return abs(det(l.t-l.s,p-l.s))/dis(l.s,l.t);}
ld point_to_segment(const point&p,const line&l){
/*点 p 到线段 l 距离*/
if(l.s==l.t||sgn(dot(l.s-p,l.t-l.s))*sgn(dot(l.t-p,l.t-l.s))>0)
return min(dis(p,l.s),dis(p,l.t));
return point_to_line(p,l);}
#define ist(i) while(c.size()>f&&!turn_left(*prev(c.end()),*prev(prev(c.end())),a[i]))c.pop_back();c.push_back(a[i]);
vector<point> Andrew(vector<point>a){
/*极角序求点集 a 的凸包*/
if(a.size()<=2)return a;
stable_sort(a.begin(),a.end());
vector<point> c;int f=1;for(int i=0;i<(int)a.size();i++){ist(i)}
f=c.size();for(int i=(int)a.size()-2;i>=0;i--){ist(i)}
c.pop_back();
return c;
}
ld area(vector<point>&a){
/*求简单多边形 a 的面积*/
ld ret=0;
for(int i=0;i<a.size();i++)
ret+=det(a[i],a[(i+1)%a.size()]);
return abs(ret/2);
}
bool inside(point p,vector<point>&a){
/*判断点 p 是否在凸包 a 内部*/
for(int i=0;i<a.size();i++)
if(!turn_left(a[i],a[(i+1)%a.size()],p))return 0;
return 1;
}
bool inter_judge2(const line&a,const line&b){
return point_on_segment(a.t,b)||two_side(a.s,a.t,b)&&two_side(b.s,b.t,a);}
point p[505];vector<point> w,id;
bool v[505];int n,m,ans=1;
vector<int> ok[505];
int t[505][505][2],nx[505][505][2];
int ccc[505][505];
int calc(int i,int j,int k){
if(i>j)swap(i,j);if(i>k)swap(i,k);if(j>k)swap(j,k);
//cerr<<p[i].x<<" "<<p[i].y<<" "<<p[j].x<<" "<<p[j].y<<" "<<p[k].x<<" "<<p[k].y<<"\n";
// //cerr<<i<<" "<<j<<" "<<k<<"\n";
if(p[i].x==p[j].x)return abs(ccc[i][j]+ccc[j][k]+ccc[k][i]-2);
if(p[j].x==p[k].x)return abs(ccc[i][j]+ccc[j][k]+ccc[k][i]-1);
return abs(ccc[i][j]+ccc[j][k]+ccc[k][i])-turn_left(p[i],p[k],p[j]);
}
int main(){
// freopen("in.in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y;stable_sort(p+1,p+n+1);
for(int i=1;i<=n;i++)p[i].c=i,w.push_back(p[i]);id=Andrew(w);m=id.size();
// if(n==500)for(int i=1;i<=70;i++)cout<<p[i].x<<" "<<p[i].y<<" ";
for(auto j:id)v[j.c]=1;//cerr<<1;
for(int i=1;i<=n;i++){//cerr<<i<<"\n";
for(int j=i+1;j<=n;j++){
for(int k=1;k<=n;k++)
ccc[i][j]+=inter_judge2(line(p[i],p[j]),line(p[k],point(p[k].x,1000000)));
ccc[j][i]=-ccc[i][j];
}
}
// if(n==500)for(int i=0;i<m;i++)cout<<id[i].c<<" "<<id[i].x<<" "<<id[i].y<<"\n";
for(int i=1;i<=n;i++){if(v[i])continue;//cerr<<i<<":\n";
for(int j=0;j<m;j++){
if(calc(i,id[j].c,id[(j+1)%m].c)==0)ok[i].push_back(j),ans++;
//if(calc(i,id[j].c,id[(j+1)%m].c)==1)ans+=2;
}//cerr<<'\n';
cerr<<ans<<'\n';
}line t1,t2;int pl,x;point px;//cerr<<2;
// for(int i=1;i<=n;i++){
// if(v[i])continue;//cerr<<i<<": ";
// for(auto j:ok[i])//cerr<<j<<" ";//cerr<<'\n';
cerr<<ans<<"\n";//if(n==500)while(1);
// for(int i=1;i<=n;i++){
// if(v[i])continue;
// pl=0;x=ok[i].size();if(x==0)continue;
// for(int j=0;j<m;j++){
// t[i][j][0]=pl;
// if(j==ok[i][pl])pl=(pl+1)%x;
// //cerr<<t[i][j][0]<<" ";
// }//cerr<<"\n";
// }for(int i=1;i<=n;i++){
// if(v[i])continue;
// x=ok[i].size();pl=x-1;if(x==0)continue;
// for(int j=m-1;j>=0;j--){
// t[i][j][1]=pl;
// if(j==ok[i][pl])pl=(pl+x-1)%x;
// //cerr<<t[i][j][1]<<" ";
// }//cerr<<"\n";
// }//cerr<<3;if(n==500)cout<<m<<"\n";
// for(int i=1;i<=n;i++){if(v[i])continue;
// for(int j=1;j<=n;j++){if(v[j]||i==j)continue;
// for(int k=0;k<m;k++){
// if(parallel({p[i],p[j]},{id[k],id[(k+1)%m]}))continue;
// px=line_intersect({p[i],p[j]},{id[k],id[(k+1)%m]});//cerr<<i<<" "<<j<<" "<<px.x<<" "<<px.y<<"\n";
// if(abs(px.x-p[i].x)>=abs(px.x-p[j].x)&&abs(px.y-p[i].y)>=abs(px.y-p[j].y)&&point_on_segment(px,{id[k],id[(k+1)%m]}))
// {nx[i][j][0]=(k+1)%m;break;}
// }for(int k=m-1;k>=0;k--){
// if(parallel({p[i],p[j]},{id[k],id[(k+1)%m]}))continue;
// px=line_intersect({p[i],p[j]},{id[k],id[(k+1)%m]});//cerr<<i<<" "<<j<<" "<<px.x<<" "<<px.y<<"\n";
// if(abs(px.x-p[i].x)>=abs(px.x-p[j].x)&&abs(px.y-p[i].y)>=abs(px.y-p[j].y)&&point_on_segment(px,{id[k],id[(k+1)%m]}))
// {nx[i][j][1]=(k+m-1)%m;break;}
// }//cerr<<nx[i][j][0]<<" "<<nx[i][j][1]<<"\n";
// }
// }//if(n==500)for(int i=126;i<=250;i++){cout<<ok[i].size()<<" ";if(i%125==0)cout<<'\n';}
// for(int i=1;i<=n;i++){if(v[i]||(!ok[i].size()))continue;
// for(int j=i+1;j<=n;j++){if(v[j]||i==j||(!ok[j].size()))continue;x=ok[j].size();
// for(int k=0;k<m;k++)
// if(calc(i,id[k].c,id[k+1].c)==0&&calc(i,j,id[(k+1)%m].c)==0&&calc(j,id[k].c,id[(k+1)%m].c)==0)ans++;
// cerr<<ans<<"\n";
// for(auto k:ok[i]){
// t1={p[j],id[(k+1)%m]},t2={p[i],id[k]};
// if(inter_judge(t1,t2))
// ans+=(t[j][(k+m-1)%m][1]-t[j][nx[j][i][0]][0]+x+1)%x;
// else{
// t1={p[j],id[k]},t2={p[i],id[(k+1)%m]};
// if(inter_judge(t1,t2))
// ans+=(t[j][nx[j][i][1]][1]-t[j][(k+1)%m][0]+x+1)%x;
// else ans+=x;
// }cerr<<ans<<"\n";
// }
// }
// }
cout<<ans;
// for(int i=1;i<=n;i++)
// for(int j=i+1;j<=n;j++)
// for(int k=j+1;k<=n;k++)
//cerr<<i<<' '<<j<<' '<<k<<' '<<calc(i,j,k)<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3884kb
input:
7 1 4 4 0 2 3 3 1 3 5 0 0 2 4
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
5 4 0 0 0 2 1 3 3 3 1
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
6 0 0 3 0 3 2 0 2 1 1 2 1
output:
7
result:
ok 1 number(s): "7"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Runtime Error
input:
2000 86166 617851 383354 -277127 844986 386868 -577988 453392 -341125 -386775 -543914 -210860 -429613 606701 -343534 893727 841399 339305 446761 -327040 -218558 -907983 787284 361823 950395 287044 -351577 -843823 -198755 138512 -306560 -483261 -487474 -857400 885637 -240518 -297576 603522 -748283 33...