二分，求直线上覆盖所有点的最短时间

http://codeforces.com/group/aUVPeyEnI2/contest/230300/problem/E

solution：

``` 1 /*************************************************************************
2     > File Name:
3     > Author: QWX
4     > Mail:
5     > Created Time: 2018/10/11 18:11:28
6  ************************************************************************/
7
8
9 //{{{ #include
10 #include<iostream>
11 #include<cstdio>
12 #include<algorithm>
13 #include<vector>
14 #include<cmath>
15 #include<queue>
16 #include<map>
17 #include<set>
18 #include<string>
19 #include<cstring>
20 #include<complex>
21 #include<bits/stdc++.h>
22 #define mp make_pair
23 #define pb push_back
24 #define first fi
25 #define second se
26 #define pw(x) (1ll << (x))
27 #define sz(x) ((int)(x).size())
28 #define all(x) (x).begin(),(x).end()
29 #define rep(i,l,r) for(int i=(l);i<(r);i++)
30 #define per(i,r,l) for(int i=(r);i>=(l);i--)
31 #define FOR(i,l,r) for(int i=(l);i<=(r);i++)
32 #define cl(a,b) memset(a,b,sizeof(a))
33 #define fastio ios::sync_with_stdio(false);cin.tie(0);
34 #define lson l , mid , ls
35 #define rson mid + 1 , r , rs
36 #define INF 0x3f3f3f3f
37 #define LINF 0x3f3f3f3f3f3f3f3f
38 #define ll long long
39 #define ull unsigned long long
40 #define dd(x) cout << #x << " = " << (x) << ","
41 #define de(x) cout << #x << " = " << (x) << "\n"
42 #define endl "\n"
43 using namespace std;
44 //}}}
45
46 const int N=1e5+7;
47 ll a[N],b[N];
48 int n,m;
49 bool check(ll t)
50 {
51     int cnt=0;
52     rep(i,0,n){
53         if(t<abs(a[i]-b[cnt]))continue;
54         ll d=a[i];
55         if(a[i]<b[cnt])d+=t;
56         else d+=max((t-(a[i]-b[cnt]))/2,t-2*(a[i]-b[cnt]));
57         while(cnt<m&&b[cnt]<=d)cnt++;
58     }
59     return cnt>=m;
60 }
61
62 int main()
63 {
64     fastio;
65     cin>>n>>m;
66     rep(i,0,n)cin>>a[i];
67     rep(i,0,m)cin>>b[i];
68     ll l=0,r=1e11,ans=0;
69     while(l<=r){
70         ll mid=(l+r)>>1;
71         if(check(mid))r=mid-1,ans=mid;
72         else l=mid+1;
73     }
74     cout<<ans<<endl;
75     return 0;
76 }```

求直线与线段的交点

1,求点到直线的带符号距离: float getSignedDistance(点P,直线AB) //求点P到直线AB的带符号距离(当P在AB左侧时距离为正,右侧时为负) { dir=直线AB的方向向量 根据dir求出直线AB的左手法线向量leftNormal = (-dir.y,dir.x).normalized 线段AP在leftNormal上的投影即为P到直线AB的带符号距离: signedDistance=dot(AP,leftNormal); return signedDistance;

hdu 3641 数论 二分求符合条件的最小值数学杂题

http://acm.hdu.edu.cn/showproblem.php?pid=3641 学到: 1.二分求符合条件的最小值 /*==================================================== 二分查找符合条件的最小值 ======================================================*/ ll solve() { __int64 low = 0, high = INF, mid ; while(low <=

3403: [Usaco2009 Open]Cow Line 直线上的牛

3403: [Usaco2009 Open]Cow Line 直线上的牛 Time Limit: 3 Sec  Memory Limit: 128 MBSubmit: 71  Solved: 62[Submit][Status] Description 题目描述 约翰的N只奶牛(编为1到N号)正在直线上排队．直线上开始的时候一只牛也没有．接下来发生了S(1≤S≤100000)次事件,一次事件可能是以下四种情况之一: ．一只奶牛加入队伍的左边(输入“AL”)． ．一只奶牛加入队伍的右边(输入“AR

HDU - 1588 Gauss Fibonacci （矩阵快速幂+二分求等比数列和）

Description Without expecting, Angel replied quickly.She says: "I'v heard that you'r a very clever boy. So if you wanna me be your GF, you should solve the problem called GF~. " How good an opportunity that Gardon can not give up! The "Prob