记录：P11370 [Ynoi2024] 堕天作战/虚空处刑
Tests
这里是一些调试的时候用到的数据。
Test #0
样例调了好一会。1 pt -> 10 pts。
Test #1
从数据里偷的，一边加一坨调试语句一边调，不熟练，搞了两个小时，10 pts -> 8 pts。最后发现有两个 bug：
- 分数结构体构造函数中传进去的和实际成员变量名重名，修改的是参数（我之前不修改，没遇到过这个问题）。
- 有一处 lx 和 rx 写反了。
后面的数据都是拍的。
Test #2
Bug 在判断直线和凸包相交二分时应该去掉一个端点，否则二分时会有无穷大斜率。8 pts -> 12 pts。
Test #3
Bug 在某个地方 ly 和 ry 写反了。12 pts -> 50 pts。
Test #4
Bug 在垂直于 x 坐标的处理上面写挂了。50 pts -> 50 pts。
图片丢了。
Test #5
Bug 在划分多边形的块的时候，如果连接的点在分治区间外部，那么应该视为断开。50 pts -> 47 pts。
Test #6
Bug 在当询问直线直接与分治区间的端点直线上的区间相交时，没有先排序。47 pts -> 58 pts。
Test #7
Bug 在合并凸包的时候指针写挂了。58 pts -> 69 pts。
Test #8
Bug 在合并凸包的时候最靠边的点要钦定，否则会有斜率无穷大的情况。69 pts -> 71 pts。
Test #9
Bug 在判断点是否在凸包里的时候写挂了。71 pts -> 91 pts。
卡常
此时已经可以过 QOJ 数据（时限 4s，用时 2.2 秒）了，由于是 Ynoi，我们需要卡进 2 秒。卡常小技巧：所有计算答案的地方，如果已经确定相交就 continue。
Generator
附一篇用来对拍的数据生成器：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define i128 __int128
constexpr int N=200000;
struct Point{
int x,y;
Point(){}
Point(int x,int y):x(x),y(y){}
inline void read(){
scanf("%d%d",&x,&y);
}
inline int section(){
return (y==0?x:y)>0;
}
inline Point rotate(){
return Point(-y,x);
}
inline friend Point operator+(const Point a,const Point b){
return Point(a.x+a.x,a.y+b.y);
}
inline friend Point operator-(const Point a,const Point b){
return Point(a.x-b.x,a.y-b.y);
}
inline friend ll operator*(const Point a,const Point b){
return 1ll*a.x*b.x+1ll*a.y*b.y;
}
inline friend ll cross(const Point a,const Point b){
return 1ll*a.x*b.y-1ll*a.y*b.x;
}
inline friend double area(Point a,Point b,Point c){
return cross(b-a,c-a)/2.0;
}
inline friend double distance(const Point a,const Point b){
return hypot<double>(a.x-b.x,a.y-b.y);
}
inline friend bool operator<(Point a,Point b){
return a.section()!=b.section()?a.section()>b.section():cross(a,b)>0;
}
};
struct Segment{
Point u,v;
Segment(){}
Segment(Point u,Point v):u(u),v(v){}
inline friend bool on(const Point &x,const Segment &y){
return cross(y.v-y.u,x-y.u)==0&&(x-y.u)*(x-y.v)<=0;
}
inline friend bool intersection(const Segment &x,const Segment &y){
ll c1=cross(x.v-x.u,y.u-x.u),c2=cross(x.v-x.u,y.v-x.u),c3=cross(y.v-y.u,x.u-y.u),c4=cross(y.v-y.u,x.v-y.u);
if((i128)c1*c2<0&&(i128)c3*c4<0)return true;
return c1==0&&on(y.u,x)||c2==0&&on(y.v,x)||c3==0&&on(x.u,y)||c4==0&&on(x.v,y);
}
};
int n=10,q=200000,V=1000;
Point a[200001];
Segment seg[200001];
mt19937 mt_rand(random_device{}());
int rnd(int l,int r){
return mt_rand()%(r-l+1)+l;
}
int main(){
n=rnd(3,10),V=rnd(n,rnd(n,n*3));
bool flag;
do{
for(int i=1;i<=n;i++)a[i]=Point(rnd(1,V),rnd(1,V));
for(int i=1;i<=n;i++)seg[i]=Segment(a[i],a[i==n?1:i+1]);
flag=false;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)flag|=a[i].x==a[j].x&&a[i].y==a[j].y;
for(int i=1;i<=n;i++)
for(int j=i+2;j<=n;j++)
if(i!=1||j!=n)flag|=intersection(seg[i],seg[j]);
for(int i=1;i<=n;i++){
Point x=a[i],y=a[i==n?1:i+1],z=a[i==1?n:i-1];
flag|=on(x,Segment(y,z));
}
}while(flag);
printf("%d %d\n",n,q);
for(int i=1;i<=n;i++)printf("%d %d\n",a[i].x,a[i].y);
while(q--){
int x1,y1,x2,y2;
do x1=rnd(1,V),y1=rnd(1,V),x2=rnd(1,V),y2=rnd(1,V);
while(x1==x2&&y1==y2);
printf("%d %d %d %d\n",x1,y1,x2,y2);
}
return 0;
}Brute Force
附赛时暴力代码。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr int N=200000;
struct Point{
int x,y;
Point(){}
Point(int x,int y):x(x),y(y){}
inline int section(){
return (y==0?x:y)>0;
}
inline Point rotate(){
return Point(-y,x);
}
inline friend Point operator+(const Point a,const Point b){
return Point(a.x+a.x,a.y+b.y);
}
inline friend Point operator-(const Point a,const Point b){
return Point(a.x-b.x,a.y-b.y);
}
inline friend ll operator*(const Point a,const Point b){
return 1ll*a.x*b.x+1ll*a.y*b.y;
}
inline friend ll cross(const Point a,const Point b){
return 1ll*a.x*b.y-1ll*a.y*b.x;
}
inline friend double area(Point a,Point b,Point c){
return cross(b-a,c-a)/2.0;
}
inline friend double distance(const Point a,const Point b){
return hypot<double>(a.x-b.x,a.y-b.y);
}
inline friend bool operator<(Point a,Point b){
return a.section()!=b.section()?a.section()>b.section():cross(a,b)>0;
}
}a[N+1];
int n,q;
// Thanks @Copilot
inline bool check(Point u1, Point v1, Point u2, Point v2) {
// 判断叉积的符号
auto cross1 = cross(v1 - u1, u2 - u1);
auto cross2 = cross(v1 - u1, v2 - u1);
auto cross3 = cross(v2 - u2, u1 - u2);
auto cross4 = cross(v2 - u2, v1 - u2);
// 判断两条线段是否相交
if (cross1 * cross2 < 0 && cross3 * cross4 < 0) {
return true;
}
// 处理共线的情况，判断端点是否在线段上
// u2, v2 在 u1-v1 上
if (cross1 == 0 && (u1.x <= u2.x && u2.x <= v1.x || u1.x >= u2.x && u2.x >= v1.x) &&
(u1.y <= u2.y && u2.y <= v1.y || u1.y >= u2.y && u2.y >= v1.y)) {
return true;
}
if (cross2 == 0 && (u1.x <= v2.x && v2.x <= v1.x || u1.x >= v2.x && v2.x >= v1.x) &&
(u1.y <= v2.y && v2.y <= v1.y || u1.y >= v2.y && v2.y >= v1.y)) {
return true;
}
if (cross3 == 0 && (u2.x <= u1.x && u1.x <= v2.x || u2.x >= u1.x && u1.x >= v2.x) &&
(u2.y <= u1.y && u1.y <= v2.y || u2.y >= u1.y && u1.y >= v2.y)) {
return true;
}
if (cross4 == 0 && (u2.x <= v1.x && v1.x <= v2.x || u2.x >= v1.x && v1.x >= v2.x) &&
(u2.y <= v1.y && v1.y <= v2.y || u2.y >= v1.y && v1.y >= v2.y)) {
return true;
}
return false;
}
int main(){
freopen("geometry.in","r",stdin);
freopen("geometry.out","w",stdout);
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
while(q--){
Point u,v;
scanf("%d%d%d%d",&u.x,&u.y,&v.x,&v.y);
bool flag=false;
for(int i=1;i<=n&&!flag;i++)
flag|=check(u,v,a[i],a[i==n?1:i+1]);
puts(flag?"YES":"NO");
}
return 0;
}Codes
三份代码分别是刚写完、调出来、卡常后的版本。