CF1468I Plane Tiling 题解
前言。
本题的第一篇题解！
用到了数论几何，构造与计算几何。较为复杂的一道题。
第一次修改于
题意简述：
给定一个 YES 并输出点的坐标，否则输出 NO 结束程序。
分析。
参考官方题解，虽然很难理解。
- 方法
1 来自综合理解。
考虑有一个无限的
如图所示：
明显这是一个平面的平铺的一坨平行四边形，其中一个平行四边形的角，即我们作为基准点的那个平行四边形的顶点，分别位于
此时我们发现根据皮克定理
这样我们就将这个数论题转化为几何题了，代码复杂度为
代码如下，仅供参考：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const double eps=1e-9;
//定义一个点。
struct node{
double x,y;
node(double x=0,double y=0):x(x),y(y){}
};
//判断符号的函数。
int sig(double x){
if(fabs(x)<eps){
return 0;
}//负数判断，注意浮点。
else if(x>0){
return 1;
}//正数判断。
else return -1;//特判0的情况。
}
//浮点数的比较函数。
int exch(double x,double y){
if(fabs(x-y)<eps){
return 0;
}
else if(x>y){
return 1;
}//这个的思想就是绝对值。
else return -1;
}
//定义一个向量。
typedef node vvector;
//向量的加法。
vvector operator+(vvector a,vvector b){
return vvector(a.x+b.x,a.y+b.y);
}
//向量的减
vvector operator-(vvector a,vvector b){
return vvector(a.x-b.x,a.y-b.y);
}
//向量的数乘。
vvector operator*(vvector a,double p){
return vvector(a.x*p,a.y*p);
}
vvector operator/(vvector a,double p){
return vvector(a.x/p,a.y/p);
}
//两个点判等。
bool operator==(const node &a,const node &b){
if(exch(a.x,b.x)==0&&exch(a.y,b.y)==0){
return true;
}
else return false;
}
//点积。
double dianji(vvector a,vvector b){
return a.x*b.x+a.y*b.y;
}
//叉积。
double chaji(vvector a,vvector b){
return a.x*b.y-a.y*b.x;
}
double Mo(vvector a){
return sqrt(dianji(a,a));
}
//判断直线和线段是否相交
bool cheak(node P,vvector v,node a,node b){
double fi=chaji(v,a-P);
double se=chaji(v,b-P);
if(!sig(fi)||!sig(se)){
if(!sig(fi)&&!sig(se)){
return false;
}
else return true;
}
else return sig(fi)*sig(se)<0;
}
//计算两直线的交点(P+tv,Q+tw)。
//注意在在调用前要保证两直线相交，否则不存在交点。
node point_two(node point,vvector tv,node point_other,vvector tw){
vvector tot=point-point_other;
double cut=chaji(tw,tot)/chaji(tv,tw);
return point+tv*cut;
}
int n,dx1,dy1,dx2,dy2;
vector<pair<int,int> > ans;
node p1,p2,p3,p4,p5;
vvector v,v1,v2;
node sum1,sum2;
int ksum_1,ksum_2,du1,du2;
int main(){
cin>>n>>dx1>>dy1>>dx2>>dy2;
if(dx1<0){dx1*=-1;dy1*=-1;}
if(dx2<0){dx2*=-1;dy2*=-1;}
//处理负数的情况。
if((dx1==0&&dy1==0)||(dx2==0&&dy2==0)||(dx1==dx2&&dy1==dy2)){
cout<<"NO\n";
//cout<<"yep!\n";
return 0;
}//判断无解情况。
p1=node(dx1,dy1);
p2=node(dx2,dy2);
p3=node(0,0);
p4=node(dx1+dx2,dy1+dy2);
v=vvector(0,1);
v1=vvector(dx1,dy1);
v2=vvector(dx2,dy2);
int flag=1;
for(int i=0;i<=dx1+dx2-1;i++){
if(i==dx1+dx2){
continue;
}
p5=node(i,0);
if(cheak(p5,v,p1,p4)){
sum1=point_two(p5,v,p1,v2);
ksum_1=0;
}
else{
sum1=point_two(p5,v,p3,v1);
ksum_1=1;
//注意不要打错变量名，比如我这里之前打成了ksum_1调了10分钟。
}
if(cheak(p5,v,p2,p4)){
sum2=point_two(p5,v,p2,v1);
ksum_2=0;
}
else{
sum2=point_two(p5,v,p3,v2);
ksum_2=1;
}
if(exch(sum1.y,sum2.y)>0){
swap(sum1,sum2);
swap(ksum_1,ksum_2);
}
//进入复杂区，注意细节。
if(ksum_1==1){
if(sig(sum1.y-round(sum1.y))==0){
du1=round(sum1.y);
}
else{
if(sig(sum1.y)<0){
du1=(int)sum1.y;
}
else{
du1=(int)sum1.y+1;
}
}
}
else{
if(sig(sum1.y-round(sum1.y))==0){
du1=round(sum1.y)+1;
}
else{
if(sig(sum1.y)<0){
du1=(int)sum1.y;
}
else{
du1=(int)sum1.y+1;
}
}
}
if(ksum_2==1){
if(sig(sum2.y-round(sum2.y))==0){
du2=round(sum2.y);
}
else{
if(sig(sum2.y)<0){
du2=(int)sum2.y-1;
}
else{
du2=(int)sum2.y;
}
}
}
else{
if(sig(sum2.y-round(sum2.y))==0){
du2=round(sum2.y)-1;
}
else{
if(sig(sum2.y)<0){
du2=(int)sum2.y-1;
}
else{
du2=(int)sum2.y;
}
}
}
//cout<<du1<<" "<<du2<<"\n";
for(int j=du1;j<=du2;j++){
ans.push_back(make_pair(i,j));
if((int)(ans.size())>n){
flag=0;
break;
}
}
if(!flag){
break;
}
}
if((int)(ans.size())!=n){
cout<<"NO\n";
}
else{
cout<<"YES\n";
for(auto count:ans){
cout<<count.first<<" "<<count.second<<"\n";
}
}
return 0;
}考虑到这道题应该也有用数学方法做的，所以补充一些数学证明。
- 方法
2 来自官方题解。
首先，我们计算
其中
所以如果
定义
显然可以选择点
如何证明这样的选择是正确的呢？
假设对于某些非零对