给一个矩形和n块隔板,m个点 问隔板隔开的每个区域内有多少个点(保证不在隔板上)
n<=5000,m<=5000
首先考虑如果所有板子都是直的就是一个二分查找的标准形式
其实斜的也能一样做 因为二分的条件没变
变得就是如何判断在板子的左侧之类的
一个叉积就好了
图源自dalao https://blog.csdn.net/yskyskyer123/article/details/52107419
就是Xmlt(PA,PB)<0因为卡格所以没有共线的问题吧
复杂度O(mlgn*浮点常数)
Code:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 #include<queue> 6 #include<iostream> 7 #define ms(a,b) memset(a,b,sizeof a) 8 #define rep(i,a,n) for(int i = a;i <= n;i++) 9 #define per(i,n,a) for(int i = n;i >= a;i--) 10 #define inf 2147483647 11 using namespace std; 12 typedef long long ll; 13 typedef double D; 14 #define eps 1e-8 15 ll read() { 16 ll as = 0,fu = 1; 17 char c = getchar(); 18 while(c < '0' || c > '9') { 19 if(c == '-') fu = -1; 20 c = getchar(); 21 } 22 while(c >= '0' && c <= '9') { 23 as = as * 10 + c - '0'; 24 c = getchar(); 25 } 26 return as * fu; 27 } 28 //head 29 #define P point 30 struct point { 31 D x,y; 32 point(){} 33 point(D X,D Y):x(X),y(Y){} 34 D len() {return sqrt(x*x+y*y);} 35 D tan() {return y/x;} 36 D sin() {return len() / y;} 37 D cos() {return len() / x;} 38 void read() {scanf("%lf%lf",&x,&y);} 39 void print() {printf("%.2lf %.2lf ",x,y);} 40 friend inline point operator + (const point &a,const point &b) { 41 return point(a.x+b.x,a.y+b.y); 42 } 43 friend inline point operator - (const point &a,const point &b) { 44 return point(a.x-b.x,a.y-b.y); 45 } 46 //放缩 47 friend inline point operator * (const point &a,const D &b) { 48 return point(a.x*b,a.y*b); 49 } 50 //叉积 51 friend inline D operator * (const point &a,const point &b) { 52 return a.x*b.y-a.y*b.x; 53 } 54 //点积 55 friend inline D operator / (const point &a,const point &b) { 56 return a.x*b.x+a.y*b.y; 57 } 58 }; 59 struct line { 60 D k,b; 61 void init(point x,point y) { 62 k = (y.y-x.y)/(y.x-x.x); 63 b = x.y - k * x.x; 64 } 65 D YY(D X) {return k*X+b;} 66 D XX(D Y) {return (Y-b)/k;} 67 }; 68 struct yuan { 69 D r,x,y; 70 yuan(){} 71 yuan(int R,int X,int Y):r(R),x(X),y(Y){} 72 }; 73 bool ONSEG(point a,point b,point p) { 74 return ((a-b).len() == (a-p).len() + (p-b).len()); 75 } 76 D TRIAREA(point a,point b,point c) { 77 return ((a-b)*(a-c)) / 2.0; 78 } 79 #define ONLINE(a,b,c) (((a-b)*(a-c)) == 0) 80 #define sign(x) (x) > 0 ? 1 : ((x) < 0 ? -1 : 0) 81 // 1 0 -1 82 // 锐 直 钝 83 int ANGDIR(point a,point b,point p) { 84 D ans = (p-a)*(p-b); 85 return sign(ans); 86 } 87 88 D dis(point a,point b,point p) { 89 if(ANGDIR(b,p,a) == -1) return (p-a).len(); 90 if(ANGDIR(a,p,b) == -1) return (p-b).len(); 91 return ((p-a)*(p-b)) / (a-b).len(); 92 } 93 D dis(point a,line l) { 94 return (l.k * a.x - a.y + l.b) / sqrt(l.k*l.k+1); 95 } 96 int cross(P a,P b,P c,P d) { 97 if(ONLINE(a,b,c) ^ ONLINE(a,b,d)) return 1; 98 if(ONLINE(c,d,a) ^ ONLINE(c,d,b)) return 1; 99 if(ONLINE(a,b,c) & ONLINE(a,b,d)) return -1; 100 if(ONLINE(c,d,a) & ONLINE(c,d,b)) return -1; 101 D J1 = ((c-d)*(c-a)) * ((c-d)*(c-b)); 102 D J2 = ((a-b)*(a-c)) * ((a-b)*(a-d)); 103 if(J1 < 0 && J2 < 0) return 1; 104 return 0; 105 } 106 point Cross(point a,point b,point c,point d) { 107 if(ONLINE(a,b,c)) return c; 108 if(ONLINE(a,b,d)) return d; 109 if(ONLINE(c,d,a)) return a; 110 if(ONLINE(c,d,b)) return b; 111 D S1 = (a-c)*(a-d),S2 = (b-d) * (b-c); 112 point tmp = (b-a) * (S1 / (S1+S2)); 113 return a + tmp; 114 } 115 //CP 116 const int N = 100003; 117 int n,T; 118 D X1,Y1,X2,Y2; 119 int cnt[N]; 120 struct seg { 121 point a,b; 122 }p[N]; 123 point aim; 124 bool check(int i) { 125 return (aim - p[i].a) * (aim - p[i].b) < 0; 126 } 127 128 void solve() { 129 aim.read(); 130 int L = 0,R = n+1; 131 while(R > L) { 132 int m = L+R >> 1; 133 if(check(m)) R = m; 134 else L = m+1; 135 } 136 cnt[L]++; 137 } 138 139 int main() { 140 while(1) { 141 n = read(); 142 if(!n) return 0; 143 T = read(); 144 X1 = read(),Y1 = read(),X2 = read(),Y2 = read(); 145 rep(i,1,n) { 146 p[i].a = point(read(),Y1); 147 p[i].b = point(read(),Y2); 148 } 149 ms(cnt,0); 150 rep(i,1,T) solve(); 151 rep(i,1,n+1) printf("%d: %d ",i-1,cnt[i]); 152 puts(""); 153 } 154 }
一堆函数没什么用qwq