UVa LA 4253 UVa 1421 Archery 枚举，状态削减，oj错误题目 难度: 1
題目
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4167
?
題意
有n+1條平行于x軸的線段，最底下的線段是[0, w]，站在最下面的第0條線段上的某個點上，問有沒有一條過該點的直線也通過上面的n條線段。2<=n<=5000，2<=w<=1e7，保證這n+1條線段高度都不同。最高的線段到第0條線段高度差（y坐標差）不超過n，數據保證每條線段高度不同。對于第i條線段，其左右端點橫坐標Li，Ri必然滿足0<=Li<Ri<=W。第i條線段高度Di滿足0<=Di<=W。Li,Ri,Di都是整數，這樣精度問題較小。
?
思路
想到直線就會想到兩點式或者點斜式。這里兩點式一定會TLE。因此只能是點斜式了，枚舉斜率并不是一個很好的做法。因此，可以枚舉直線上一點，然后通過斜率來看有沒有符合結果的直線。由于直線可以平移，因此總可以平移到一種同時經過第i條線段左端點和第k條線段右端點的情況。因此只需要枚舉這n+1條線段的左端點。
對于第i條線段的左端點(Li,Di)，如果有一條經過(Li,Di)的直線經過全部n+1條線段，則可以輸出"YES"，否則，還要繼續枚舉下一線段的左端點。或者可以說，如對(Li,Di)，存在斜率k（k可能為無窮）使得對應直線經過全部n+1條線段，則滿足題意
由于線段是平行于x軸的，所以不會產生跨x軸的情況，那么就可以維護每條肽段所對應的可行斜率的集合，如果這些集合的并集非空，那么就有符合結果的直線存在。
但是直接維護斜率存在要過90度的情況，因此，可以以(Li,Di)為中心建立極坐標系，維護線段所對應角度。如果比Di高，對應區間為(Ri, Di)對應極角到(Li, Di)對應極角這個封閉區間。如果比Di低，也就是在x軸下方，總可以不失意義轉換為x軸上方的對應方向相反的區間。
?
感想：
1. 注意如果把scanf("%d%d", R, &n) == 2作為判斷條件，就會wa，這一般是因為測試數據中有冗余
2. 一開始枚舉了兩條線段的端點<左，左>，<左，右>，<右，左>，<右，右>四種情況，所以一直TLE。但是因為必然可以平移到既有左端點又有右端點，所以直接枚舉遍歷左或者右端點就夠了
3. 精度倒不用特別注意
代碼
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <vector> #include <map> #include <set> using namespace std; typedef pair<int, int> Pair; typedef long long ll; const int MAXN = 5e3 + 4; const double pie = acos(-1.0); int n; int D[MAXN]; int L[MAXN]; int R[MAXN]; bool simplecheck() {int mnX = 0;int mxX = R[0];for (int i = 0; i <= n; i++) {mnX = max(mnX, L[i]);mxX = min(mxX, R[i]);}return mnX <= mxX;}double getK(int x0, int x1, int y0, int y1) {return (y1 - y0) * 1.0 / (x1 - x0); }double getAng(int x0, int x1, int y0, int y1) {if (x0 == x1)return pie / 2;double ang = atan(getK(x0, x1, y0, y1));if (ang < 0)return ang + pie;return ang; }void getAngInterval(int x0, int y0, int i, double& a0, double& a1) {if (D[i] == y0) {a0 = 0;a1 = pie;}else if (D[i] > y0) {a0 = getAng(x0, R[i], y0, D[i]);a1 = getAng(x0, L[i], y0, D[i]);}else {a0 = getAng(x0, L[i], y0, D[i]);a1 = getAng(x0, R[i], y0, D[i]);} } int main() {int T;freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\input.txt", "r", stdin);freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\output.txt", "w", stdout);scanf("%d", &T);//cin >> T;for (int ti = 1; ti <= T; ti++) {scanf("%d%d", R, &n);for (int i = 1; i <= n; i++) {scanf("%d%d%d", D + i, L + i, R + i);}bool fl = simplecheck();if (!fl) {for (int i = 0; i <= n; i++) {double amn = 0, amx = pie;bool ok = true;for (int j = 0; j <= n && ok; j++) {double amnnow, amxnow;getAngInterval(L[i], D[i], j, amnnow, amxnow);if (amnnow > amx) {ok = false;break;}if (amxnow < amn) {ok = false;break;}amn = max(amn, amnnow);amx = min(amx, amxnow); //printf("From (%d, %d) to (%d, %d)->(%d, %d), ang [%.2f, %.2f], Overall [%.2f, %.2f]\n", L[i], D[i], L[j], D[j], R[j], D[j], amnnow * 180.0 / pie, amxnow * 180.0 / pie, amn * 180.0 / pie, amx * 180.0 / pie); }if (ok) {fl = true;break;}}}if (fl) {puts("YES");}else puts("NO");}return 0; } View Code?
轉載于:https://www.cnblogs.com/xuesu/p/10993209.html
總結
以上是生活随笔為你收集整理的UVa LA 4253 UVa 1421 Archery 枚举，状态削减，oj错误题目 难度: 1的全部內容，希望文章能夠幫你解決所遇到的問題。
