題目在 https://zerojudge.tw/ShowProblem?problemid=d084
這題有點複雜, 測資感覺有點陷阱. 雖然我沒有看到測資, 但是從錯誤的情況, 可以猜出是怎樣的測資導致測不過.
由於需要計算經過每棟大樓的(x,y)座標, 所以選用公式y=mx+k, 用x就可以得到y. 這公式缺點是如果P,Q兩點(x,y)都相同, 則m,k無唯一解. 所以要先判斷是否是這種情形.
這種情形下, 如果Pz==Qz, 可能是同步衛星, 不可能撞到. 如果Pz!=Qz, 那就直直往地面撞去, 似乎不用管大樓高度是否為0, 直接輸出大樓編號即可, 否則測資#5會錯.
if(Px==Qx){ //垂直軌道
if(Py==Qy) { //同步衛星或垂直降落
if(Pz==Qz){ //同步衛星
if(xy[int(Py/10)][int(Px/10)]>0){ //有房子
if(xy[int(Py/10)][int(Px/10)]>=Pz){
//這情況應該不會發生
PRINT(Px/10, Py/10);
return 0;
}else{
PRINT(-1, -1);
return 0;
}
}else{ //無房子
PRINT(-1, -1);
return 0;
}
}
else { //垂直降落
if(xy[int(Py/10)][int(Px/10)]>0){ //有房子
PRINT(Px/10, Py/10);
return 0;
}else{ //無房子
//直接撞街道, 該街道的房子編號 (#5錯誤在此)
//PRINT(-1, -1); //測資似乎有bug
PRINT(Px/10, Py/10);
return 0;
}
}
}
...再來考慮另一種情形,如果Px==Qx, 公式y=mx+k的m為無限大. 所以就乾脆直接計算從x=Qx的直線撞到哪棟大樓即可.
//Pz = Py * Mzy + Kzy (由y計算衛星高度公式)
float Mzy = (Pz-Qz)/(Py-Qy);
float Kzy = Pz-Py*Mzy;
int x = Px/10;
if(Py>Qy){
//Z由北往南降低 (由PQ決定方向, 若由斜率決定, 斜率為0時會誤判)
for(int y=int(Qy/10);y>=0;y--) //由Qy開始算
{
float sat_z=y*10*Mzy+Kzy;
if(xy[y][x]>=sat_z){
PRINT(x,y);
return 0;
}
}
}else{ //Z由南往北降低
for(int y=int(Qy/10);y<Sy;y++)
{
float sat_z=(y+1)*10*Mzy+Kzy;
if(xy[y][x]>=sat_z){
PRINT(x,y);
return 0;
}
}
}
PRINT(-1, -1);
return 0;現在可以求y=mx+k的m和k了, 然後求Q點當起始點, 直到衛星離開城市邊緣的座標R(Rx.Ry).
須注意衛星飛行的方向是由P點向Q點. 不要由Pz或Qz的高度或斜率判斷, 因為有可能遇到Pz等於Qz時,無法確定方向.
//在城市邊緣x=0, x=Sx*10, y=0, y=Sy*10,找與衛星在xy平面上的終點座標R(Rx,Ry)
float Rx=0,Ry=0;
//由Q點開始找離開城市邊緣的結束座標 (Rx,Ry)
if(Px<Qx){
//when x=10*Sx, y=m*(10*Sx)+k
float y=m*(10*Sx)+k;
if(y>=0 && y<=Sy*10){//Rx 在 10*Sx
Rx=10*Sx;
Ry=y;
}else{
if(Py<Qy){ //Ry在Sy*10
//when y=Sy*10, x=(Sy*10-k)/m;
Rx=((10*Sy)-k)/m;
Ry=Sy*10;
}else{ //Ry在0
Rx=-k/m;
Ry=0;
}
}
}else{ //when Px>Qx
//when x=0, y_Sx=k
if(k>=0 && k<=Sy*10){
Rx=0;
Ry=k;
}else{
if(Py<Qy){ //Ry在Sy*10
//when y=Sy*10, x=(Sy*10-k)/m;
Rx=((10*Sy)-k)/m;
Ry=Sy*10;
}else{ //Ry在0
Rx=-k/m;
Ry=0;
}
}
}現在有了起點(Qx, Qy)終點(Rx,Ry),就可以計算經過的高樓. 須注意Q點前的其他高樓不要去測試, 否則測資#7會不過. (我剛開始就是從城市邊緣為起點, 計算到城市另一邊緣, 照道理應該不會存在Q點前會撞到的高樓, 否則衛星早就墜毀, 但測資#7似乎不是如此)
測試有沒有撞毀高樓的方式就是計算高樓的邊緣高度有沒有比衛星高. 由於高樓的邊緣座標都位在10的倍數的地方, 所以X和Y在Q,R之間的所有10的倍數都計算就可以了, 還要記得起點Q和終點R也要計算. 所有計算的點依X排序, 方向則依P到Q的方向.
//y_middle[]加入y在10倍數處的中間點
if(Py>Qy){
for(float y=MaxY;y>=MinY;y-=10){
float y2=(int(y/10))*10;
if(y2>=MinY){
y_middle[y_middle_count][1]=y2;
y_middle[y_middle_count++][0]= (y2-k)/m;
}
}
}else{
for(float y=MinY;y<=MaxY;y+=10){
float y2=(int(y/10)+1.0)*10;
if(y2<=MaxY){
y_middle[y_middle_count][1]=y2;
y_middle[y_middle_count++][0]= (y2-k)/m;
}
}
}
...每前後兩個點, 代表進入高樓和離開高樓的點. 離開高樓的點比較低, 所以就用第二點來計算衛星高度.
高樓的座標就是由前後兩點的平均((x1+x2)/2/10, (y1+y2)/2/10).
//測試每兩個交點之間的那棟大樓, 有沒有被衛星撞上
//衛星高度用第二個點來計算
float x1=sorted[0][0];
float y1=sorted[0][1];
for(int i=1;i<sorted_count;i++){
float x2=sorted[i][0];
float y2=sorted[i][1];
float sat_h = x2*Mzx+Kzx;
int buildind_x = (x1+x2)/20;
int buildind_y = (y1+y2)/20;
int buildind_h = xy[buildind_y][buildind_x];
if(sat_h<=xy[buildind_y][buildind_x]){
PRINT(buildind_x,buildind_y);
return 0;
}
x1=x2;
y1=y2;
}完整程式如下
#include <stdio.h>
#include <math.h>
#include <cmath>
using namespace std;
int xy[1000][1000];
void PRINT(int x, int y){
printf("%d %d",x, y);
char c;
scanf("%c %c", &c);
}
float y_middle[1001][2];
int y_middle_count=0;
float sorted[2000][2];
int sorted_count=0;
int main(){
int M1,M2,N1,N2;
float Px,Py,Pz,Qx,Qy,Qz;
scanf("%d %d %f %f %f", &M1, &M2, &Px, &Py, &Pz);
scanf("%d %d %f %f %f", &N1, &N2, &Qx, &Qy, &Qz);
int Sx,Sy;
scanf("%d %d",&Sx, &Sy);
for(int i=0;i<Sy;i++){
for(int j=0;j<Sx;j++){
scanf("%d",&xy[i][j]);
}
}
//因為衛星PQ高度都已經在城市上方, 所以不用判斷衛星會不會經過城市
if(Px==Qx){ //垂直軌道
if(Py==Qy) { //同步衛星或垂直降落
if(Pz==Qz){ //同步衛星
if(xy[int(Py/10)][int(Px/10)]>0){ //有房子
if(xy[int(Py/10)][int(Px/10)]>=Pz){ //這情況應該不會發生
PRINT(Px/10, Py/10);
return 0;
}else{
PRINT(-1, -1);
return 0;
}
}else{ //無房子
PRINT(-1, -1);
return 0;
}
}
else { //垂直降落
if(xy[int(Py/10)][int(Px/10)]>0){ //有房子
PRINT(Px/10, Py/10);
return 0;
}else{ //無房子
//直接撞街道, 該街道的房子編號 (#5錯誤在此)
//PRINT(-1, -1); //測資似乎有bug
PRINT(Px/10, Py/10);
return 0;
}
}
}
//Pz = Py * Mzy + Kzy
float Mzy = (Pz-Qz)/(Py-Qy);
float Kzy = Pz-Py*Mzy;
int x = Px/10;
if(Py>Qy){ //Z由北往南降低 (由PQ決定方向, 若由斜率決定, 斜率為0時會誤判)
for(int y=int(Qy/10);y>=0;y--) //由Qy開始算
{
float sat_z=y*10*Mzy+Kzy;
if(xy[y][x]>=sat_z){
PRINT(x,y);
return 0;
}
}
}else{ //Z由南往北降低
for(int y=int(Qy/10);y<Sy;y++)
{
float sat_z=(y+1)*10*Mzy+Kzy;
if(xy[y][x]>=sat_z){
PRINT(x,y);
return 0;
}
}
}
PRINT(-1, -1);
return 0;
}
//計算衛星在xy平面軌道的斜率m,截距k (y=mk+k)
float m=(Py-Qy)/(Px-Qx);
float k=Py-m*Px;
//printf("m=%f k=%f\n", m,k);
//在城市邊緣x=0, x=Sx*10, y=0. y=Sy*10,找與衛星在xy平面上的終點座標R(Rx,Ry)
float Rx=0,Ry=0;
//由Q點開始找離開城市邊緣的結束座標 (Rx,Ry)
if(Px<Qx){
//when x=10*Sx, y=m*(10*Sx)+k
float y=m*(10*Sx)+k;
if(y>=0 && y<=Sy*10){//Rx 在 10*Sx
Rx=10*Sx;
Ry=y;
}else{
if(Py<Qy){ //Ry在Sy*10
//when y=Sy*10, x=(Sy*10-k)/m;
Rx=((10*Sy)-k)/m;
Ry=Sy*10;
}else{ //Ry在0
Rx=-k/m;
Ry=0;
}
}
}else{ //when Px>Qx
//when x=0, y_Sx=k
if(k>=0 && k<=Sy*10){
Rx=0;
Ry=k;
}else{
if(Py<Qy){ //Ry在Sy*10
//when y=Sy*10, x=(Sy*10-k)/m;
Rx=((10*Sy)-k)/m;
Ry=Sy*10;
}else{ //Ry在0
Rx=-k/m;
Ry=0;
}
}
}
//由x計算z
//Pz = Px * Mzx + Kzx
float Mzx = (Pz-Qz)/(Px-Qx);
float Kzx = Pz-Px*Mzx;
//#1 #2 #7 錯誤在下面
float MaxX=(Qx>=Rx? Qx:Rx);
float MinX=(Qx< Rx? Qx:Rx);
float MaxY=(Qy>=Ry? Qy:Ry);
float MinY=(Qy< Ry? Qy:Ry);
//y_middle[]加入y在10倍數處的中間點
if(Py>Qy){
for(float y=MaxY;y>=MinY;y-=10){
float y2=(int(y/10))*10;
if(y2>=MinY){
y_middle[y_middle_count][1]=y2;
y_middle[y_middle_count++][0]= (y2-k)/m;
}
}
}else{
for(float y=MinY;y<=MaxY;y+=10){
float y2=(int(y/10)+1.0)*10;
if(y2<=MaxY){
y_middle[y_middle_count][1]=y2;
y_middle[y_middle_count++][0]= (y2-k)/m;
}
}
}
//sorted by x;
if(Px<Qx){
//加入起點
float x=MinX;
float y=x*m+k;
sorted[sorted_count][0]=x;
sorted[sorted_count][1]=y;
sorted_count++;
//加入x在10倍數處的中間點 ,並依x順序加入y在10倍數處的中間點
int y_middle_index=0;
for(x=(int(MinX/10)+1)*10;x<=MaxX;x+=10){
if(x==sorted[sorted_count-1][0])
continue;
y=x*m+k;
while(y_middle_index<y_middle_count && y_middle[y_middle_index][0]<=x){
if(y_middle[y_middle_index][0]==sorted[sorted_count-1][0]){
y_middle_index++;
continue;
}
sorted[sorted_count][0]=y_middle[y_middle_index][0];
sorted[sorted_count][1]=y_middle[y_middle_index][1];
sorted_count++;
y_middle_index++;
}
if(x==sorted[sorted_count-1][0])
continue;
if(x<=MaxX){
sorted[sorted_count][0]=x;
sorted[sorted_count][1]=y;
sorted_count++;
}
}
//加入終點
x=MaxX;
y=x*m+k;
if(x!=sorted[sorted_count-1][0]){
sorted[sorted_count][0]=x;
sorted[sorted_count][1]=y;
sorted_count++;
}
}else{
//加入起點
float x=MaxX;
float y=x*m+k;
sorted[sorted_count][0]=x;
sorted[sorted_count][1]=y;
sorted_count++;
//加入x在10倍數處的中間點 ,並依x順序加入y在10倍數處的中間點
int y_middle_index=0;
for(x=(int(MaxX/10))*10;x>=MinX;x-=10){
if(x==sorted[sorted_count-1][0])
continue;
y=x*m+k;
while(y_middle_index<y_middle_count && y_middle[y_middle_index][0]>=x){
if(y_middle[y_middle_index][0]==sorted[sorted_count-1][0]){
y_middle_index++;
continue;
}
sorted[sorted_count][0]=y_middle[y_middle_index][0];
sorted[sorted_count][1]=y_middle[y_middle_index][1];
sorted_count++;
y_middle_index++;
}
if(x==sorted[sorted_count-1][0])
continue;
if(x>=MinX){
sorted[sorted_count][0]=x;
sorted[sorted_count][1]=y;
sorted_count++;
}
}
//加入終點
x=MinX;
y=x*m+k;
if(x!=sorted[sorted_count-1][0]){
sorted[sorted_count][0]=x;
sorted[sorted_count][1]=y;
sorted_count++;
}
}
//測試每兩個交點之間的那棟大樓, 有沒有被衛星撞上
//衛星高度用第二個點來計算
float x1=sorted[0][0];
float y1=sorted[0][1];
for(int i=1;i<sorted_count;i++){
float x2=sorted[i][0];
float y2=sorted[i][1];
float sat_h = x2*Mzx+Kzx;
//printf("\n1(%f,%f) to (%f,%f,%f)\n",x1,y1,x2,y2,sat_h);
int buildind_x = (x1+x2)/20;
int buildind_y = (y1+y2)/20;
int buildind_h = xy[buildind_y][buildind_x];
//printf("B1(%d,%d)=%d\n",buildind_x,buildind_y,buildind_h);
if(sat_h<=xy[buildind_y][buildind_x]){
PRINT(buildind_x,buildind_y);
return 0;
}
x1=x2;
y1=y2;
}
PRINT(-1, -1);
return 0;
}