你需要放置一盞燈來照亮房間的每個角落，問這是否能辦到？?

輸入包含多組數據。?
每組數據第一行是正整數n(4<=n<=100)，表示房間輪廓所形成的多邊形的頂點個數。?
接下來n行，每行表示房間的一個頂點。?
頂點按順時針的順序給出，房間輪廓多邊形的所有邊都平行于坐標軸。?
輸入以n=0表示結束。

對每組數據輸出一行。?
如果能有一種放置方法照亮房間的所有地方，輸出"Yes"，否則輸出"No"

#include<cstdio> #include<cstring> #define inf 0x3fffffff int n,ok; int x1,x2,y1,y2; //在x和y方向上的合法范圍(邊界). int x[101],y[101]; //由于是順時針讀取且平行于坐標軸，所以相鄰讀取的兩個點可以確定出x或y的范圍 int check(int px,int py,int cx,int cy){ //分別是前一個點(px,py)和當前點(cx,cy) if(px==cx){ //x相同y不同，則限制x1或x2 if(cy>py){ //當前點在之前點正上方，所以應該限制x1(因為是順時針給出點) x1=x1>cx?x1:cx;return x1<=x2?1:0;}else{ //當前點在之前點的正下方，所以應該限制x2 x2=x2<cx?x2:cx;return x2>=x1?1:0;}}else{ //同理對于y相同而x不同，則限制y1或y2 if(cx>px){y2=y2<cy?y2:cy;return y2>=y1?1:0;}else{y1=y1>cy?y1:cy;return y1<=y2?1:0;}} } int main() {while(scanf("%d",&n)==1&&n){ok=1;x1=y1=-inf,x2=y2=inf; scanf("%d%d",&x[1],&y[1]);for(int i=2;i<=n;i++){scanf("%d%d",&x[i],&y[i]);if(!ok) continue;ok=check(x[i-1],y[i-1],x[i],y[i]);}if(ok) ok=check(x[n],y[n],x[1],y[1]); //要單獨考慮最后一個點和第一個點 if(ok) printf("Yes\n");else printf("No\n");} }

?

轉載于:https://www.cnblogs.com/sulley/p/8169324.html

總結

以上是生活随笔為你收集整理的【2016计概A期末】照亮房间的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。