描述
矮人們平時有走親訪友的習慣。一天，矮人國要修一條高速公路，矮人們希望他們走親訪友的時候，能夠不必穿越高速公路，這樣會更安全一些。現(xiàn)在有M個高速公路的修建方案，請你判斷這M條高速功能是否能滿足矮人們的期望。也就是說給出平面上的N個點（矮人們的住所位置），對于M條直線（高速公路），依次判斷這N個點是否在每條直線的同一側(cè)。是輸出GOOD，不是輸出BAD。
后來從劉汝佳的書里發(fā)現(xiàn)這個算法叫旋轉(zhuǎn)卡殼，專門求對踵點的。
題解
首先可以想出一個凸包模型來，因為求出所有點的凸包后可以判斷直線如果穿過凸包，就一定不滿足題意。
問題是怎么判斷直線是否穿過凸包呢？
如果直線穿過凸包，就一定在凸包兩個最遠點的中間，最遠點可以通過下面的方法找：首先預處理記錄下凸包每個邊的斜率，再算出直線的斜率，將斜率從小到大排列，假設直線斜率是正的，二分查找第一個大于直線斜率的邊，它的起點一定是一個最遠點，可以畫圖驗證一下，因為他后面的邊斜率比它大，也就相當于走的離凸包中心越來越近。然后把斜率取相反數(shù)，再找第一個斜率大于它的邊，起點是另一個最遠點。
在實現(xiàn)時直接用atan2()函數(shù)計算角度不用算斜率。
代碼：
總時間耗費: 808ms
總內(nèi)存耗費: 4 MB
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn =
100000 +
10;
const double PI =
acos(
double(-
1));
int n;
struct Point {
double x, y;Point(
double x=
0,
double y=
0):x(x),y(y) {}
}p[maxn], ch[maxn];
typedef Point Vector;Vector
operator + (Vector A, Vector B) {
return Vector(A.x+B.x, A.y+B.y); }
Vector
operator - (Vector A, Vector B) {
return Vector(A.x-B.x, A.y-B.y); }
Vector
operator * (Vector A,
double p) {
return Vector(A.x*p, A.y*p); }
Vector
operator / (Vector A,
double p) {
return Vector(A.x/p, A.y/p); }
bool operator < (
const Vector& a,
const Vector& b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
const double eps =
1e-10;
int dcmp(
double x) {
if(
fabs(x) < eps)
return 0;
else return x <
0 ? -
1 :
1;
}
bool dcmp2(
const double& a,
const double& b) {
if(dcmp(b-a) ==
1)
return 1;
return 0;
}
bool operator == (
const Vector& a,
const Vector& b) {
return dcmp(a.x-b.x) ==
0 && dcmp(a.y-b.y) ==
0;
}
double angle(Vector v) {
double ret =
atan2(v.y, v.x);
return ret < -PI/
2 ? ret+
2*PI : ret; }
double Cross(Vector A, Vector B) {
return A.x*B.y - A.y*B.x; }
int ConvexHull() {sort(p, p+n);
int m =
0;
for(
int i =
0; i < n; i++) {
while(m >
1 && Cross(ch[m-
1]-ch[m-
2], p[i]-ch[m-
2]) <=
0) m--;ch[m++] = p[i];}
int k = m;
for(
int i = n-
2; i >=
0; i--) {
while(m > k && Cross(ch[m-
1]-ch[m-
2], p[i]-ch[m-
2]) <=
0) m--;ch[m++] = p[i];}
if(n >
1) m--;
return m;
}
double ang[maxn];
int main() {
scanf(
"%d", &n);
for(
int i =
0; i < n; i++)
scanf(
"%lf%lf", &p[i].x, &p[i].y);
int c = ConvexHull();
for(
int i =
0; i < c; i++) ang[i] = angle(ch[i+
1]-ch[i]);Point a, b;
while(
scanf(
"%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y) ==
4) {
if(n <=
1)
printf(
"GOOD\n");
else {Point u = ch[upper_bound(ang, ang+c, angle(b-a), dcmp2)-ang];Point v = ch[upper_bound(ang, ang+c, angle(a-b), dcmp2)-ang];
if(dcmp(Cross(b-a, u-a)*Cross(b-a, v-a)) < eps)
printf(
"BAD\n");
else printf(
"GOOD\n");}}
return 0;
}
總結(jié)
以上是生活随笔為你收集整理的[codevs 1302] 小矮人(2002年CEOI中欧信息学奥赛)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
