【POJ1474】監控攝像頭半平面交

2019-11-06 06:52:06

字體：大中小

來源：轉載

供稿：網友

題目描述

　　一個著名的倉庫管理公司SERKOI 請你為其安裝一套閉路監視系統，由于SERKOI 財力有限，每個房間只能安裝一臺攝像機，不過其鏡頭可以向任何方向轉換。請你寫一個程序，對于給定的房間示意圖，判斷是否有可能在這個房間中的某一位置安置一臺攝像機，使其能監視到房間的每一個角落。

題目大意

能否找到一個點，能看到多邊形的每一個部位

數據范圍

點數小于100

樣例輸入

4 0 0 0 1 1 1 1 0 8 0 0 0 2 1 2 1 1 2 1 2 2 3 2 3 0 0

樣例輸出

Floor #1 Surveillance is possible.

Floor #2 Surveillance is impossible.

解題思路

半平面交，用邊去切全圖形，如果還有部分沒有被切，則有點滿足條件

代碼原來我是用邊去切的一個比較大的矩形，結果wrong了233。

#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <cmath>#include <ctime>#define Maxn 233333using namespace std;int n,nn,m;struct Point{ double x,y;}a[Maxn],b[Maxn],c[Maxn];void Init(){ for(int i=1;i<=m;i++) scanf("%lf%lf",&b[i].x,&b[i].y); n=m; memcpy(a,b,sizeof(b));}double Cross(Point a,Point b,Point c){ return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}void AddCross(Point a,Point b,Point C,Point d){ double c1=Cross(a,d,b),c2=Cross(a,C,b); c[++nn]=(Point){(c1*C.x-c2*d.x)/(c1-c2),(c1*C.y-c2*d.y)/(c1-c2)};}void Cut(Point A,Point B){ nn=0; a[n+1]=a[1]; for(int i=1;i<=n;i++){ if(Cross(a[i],B,A)>=0){ c[++nn]=a[i]; if(Cross(a[i+1],B,A)<0)AddCross(A,B,a[i+1],a[i]); }else if(Cross(a[i+1],B,A)>0)AddCross(A,B,a[i+1],a[i]); } for(int i=1;i<=nn;i++)a[i]=c[i]; n=nn;}int main(){ int Case=0; while(scanf("%d",&m)&&m){ Init(); b[m+1]=b[1]; for(int i=1;i<=m;i++) Cut(b[i],b[i+1]); cout<<"Floor #"<<++Case<<"/n"; if(n)cout<<"Surveillance is possible./n/n"; else cout<<"Surveillance is impossible./n/n"; }}

上一篇：jExcelAPI(jxl)操作Excel2003（xls格式）表格完整示例

下一篇：5位數字黑洞