題目鏈接

(BZOJ) http://lydsy.com/JudgeOnline/problem.php?id=4814
(Luogu) https://www.luogu.org/problem/P3699

題解

寫了這么多掃描線依然不會寫。。

首先思路非常簡單，枚舉每個點，把所有的直線按照極角序排序，然后掃描線解決。（注意這里掃描線是一條從這個點出發(fā)的射線）
事件有三種: (1)插入一條線段。(2)刪除一條線段。(3)查詢某個位置與該點的連線是否被某一目前存在的直線穿過。
顯然可以用一個set維護直線，set的比較函數(shù)定義為比較這個點與當前射線的交點和當前枚舉點的距離。
細節(jié)處理: (1)對于一個三角形只有與當前枚舉點的線段夾角最大的兩條邊有用。(2)如果遇到跨過極角序分界點(\(-\pi\)或\(\pi\))，顯然可以拆成兩條線段。
精度問題:由于set判相等會有精度誤差，因此盡量不用find(), 可以記下來每條直線插入到set中的位置。另外除了求交點距離之外的部分全都可以不用double實現(xiàn)。
常數(shù)問題: 注意一定不能在排序比較函數(shù)里調(diào)用三角函數(shù)！血淋淋的教訓(xùn)……

代碼

#include<bits/stdc++.h> #define llong long long using namespace std;inline int read() {int x=0; bool f=1; int c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=0;for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');if(f) return x;return -x; }const int N = 1000; const double PI = acos(-1); const double EPS = 1e-8; inline int dcmp(double x) {return x<-EPS?-1:(x>EPS?1:0);} struct Point {llong x,y;Point() {}Point(llong _x,llong _y) {x = _x,y = _y;}inline double ang() const {return atan2(y,x);} }; typedef Point Vector; inline Point operator +(const Point &x,const Point &y) {return Point(x.x+y.x,x.y+y.y);} inline Point operator -(const Point &x,const Point &y) {return Point(x.x-y.x,x.y-y.y);} inline llong Dot(const Point &x,const Point &y) {return x.x*y.x+x.y*y.y;} inline llong Cross(const Point &x,const Point &y) {return x.x*y.y-x.y*y.x;} inline llong EuclidDist2(const Point &x,const Point &y) {return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);} inline bool operator <(const Point &x,const Point &y) {return Cross(x,y)>0;} struct Line {Point x,y;Line() {}Line(const Point &_x,const Point &_y) {x = _x,y = _y;} }; struct Triangle {Point a[3]; }; struct Query {int opt,id; Point x; double ang; } qr[N*5+3]; Triangle b[N+3]; Point a[N+3]; Line stk[N+3]; int n,m,q;Vector l; inline bool cmp_qr(const Query &x,const Query &y) {int flg = dcmp(x.ang-y.ang); return flg<0 || (flg==0 && x.opt<y.opt);} inline double calcdis(const Line &x) {double t = (double)Cross(l,x.x)/((double)Cross(x.y-x.x,l));double rx = x.x.x+(x.y.x-x.x.x)*t,ry = x.x.y+(x.y.y-x.x.y)*t;return rx*rx+ry*ry; } struct Element {Line x;Element() {}Element(Line _x) {x = _x;}inline bool operator <(const Element &arg) const{double dis1 = calcdis(x),dis2 = calcdis(arg.x);return dcmp(dis1-dis2)<0;} }; multiset<Element> s; multiset<Element>::iterator adr[N+3];int main() {scanf("%d%d",&n,&m);int ans = 0;for(int i=1; i<=n; i++) scanf("%lld%lld",&a[i].x,&a[i].y);for(int i=1; i<=m; i++) scanf("%lld%lld%lld%lld%lld%lld",&b[i].a[0].x,&b[i].a[0].y,&b[i].a[1].x,&b[i].a[1].y,&b[i].a[2].x,&b[i].a[2].y);for(int i=1; i<=n; i++){q = 0; l = Vector(-1,0); Line cur;for(int j=1; j<=m; j++){Point t[3];for(int k=0; k<3; k++) t[k] = b[j].a[k]-a[i];sort(t,t+3),stk[j].x = t[0],stk[j].y = t[2];if(stk[j].x.y>0 && stk[j].y.y<0){adr[j] = s.insert(Element(stk[j]));q++; qr[q].x = stk[j].y; qr[q].id = j; qr[q].opt = 3;q++; qr[q].x = stk[j].x; qr[q].id = j; qr[q].opt = 1;}else{q++; qr[q].x = stk[j].x; qr[q].id = j; qr[q].opt = 1;q++; qr[q].x = stk[j].y; qr[q].id = j; qr[q].opt = 3;}}for(int j=i+1; j<=n; j++) q++,qr[q].x = a[j]-a[i],qr[q].opt = 2;for(int j=1; j<=q; j++) qr[j].ang = qr[j].x.ang();sort(qr+1,qr+q+1,cmp_qr);for(int j=1; j<=q; j++){l = qr[j].x;if(qr[j].opt==1){adr[qr[j].id] = s.insert(Element(stk[qr[j].id]));}else if(qr[j].opt==3){s.erase(adr[qr[j].id]);}else if(qr[j].opt==2){if(s.empty()) ans++;else{Line mini = (*s.begin()).x;double dis1 = calcdis(mini),dis2 = qr[j].x.x*qr[j].x.x+qr[j].x.y*qr[j].x.y;if(dcmp(dis1-dis2)>0) ans++;}}}s.clear();}printf("%d\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ 4814 Luogu P3699 [CQOI2017]小Q的草稿 (计算几何、扫描线、set)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。