You re given n segments on the coordinate axis Ox and the number k. The point is satisfied if it belongs to at least k segments. Find the smallest (by the number of segments) set of segments on the coordinate axis Ox which contains all satisfied points and no others.
The first line contains two integers n and k (1 ≤ k ≤ n ≤ 106) — the number of segments and the value of k.
The next n lines contain two integers li, ri ( - 109 ≤ li ≤ ri ≤ 109) each — the endpoints of the i-th segment. The segments can degenerate and intersect each other. The segments are given in arbitrary order.
First line contains integer m — the smallest number of segments.
Next m lines contain two integers aj, bj (aj ≤ bj) — the ends of j-th segment in the answer. The segments should be listed in the order from left to right.
3 2
0 5
-3 2
3 8
2
0 2
3 5
3 2
0 5
-3 3
3 8
1
0 5
题意：给你一n条线段，一个k,问你有k跳线段以上相交的线段有多少
题解：按照 左右端点区分，x,y一起排序，找增加至k个左端点加入左答案，减少到k-1个端点加入右答案，注意一个点的线段
//meek ///#include<bits/stdc++.h> #include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <queue> #include <map> #include <set> #include <stack> #include <sstream> #include <queue> using namespace std ; typedef long long ll; #define mem(a) memset(a,0,sizeof(a)) #define pb push_back #define fi first #define se second #define MP make_pair inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘)f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=x*10+ch-‘0‘; ch=getchar(); } return x*f; } //**************************************** const int N=2000000+100; const ll INF = 1ll<<61; const int inf = 1000000007; const int mod= 1000000007; int n,k,x,y,t[N]; pair<int,int> Line[N]; vector<int >ans1,ans2; int main() { scanf("%d%d",&n,&k); int cnt = 1; for(int i=1;i<=n;i++) { scanf("%d%d",&x,&y); Line[cnt++] = MP(x,-1); Line[cnt++] = MP(y,1); } sort(Line+1,Line+cnt); for(int i=1;i<cnt;i++) { t[i] = t[i-1] - Line[i].se; if(t[i]==k&&t[i-1]==k-1) ans1.pb(Line[i].fi); } memset(t,0,sizeof(t)); for(int i=1;i<cnt;i++) { t[i] = t[i-1] - Line[i].se; if(t[i]==k-1&&t[i-1]==k) ans2.pb(Line[i].fi); } if(ans1.size()!=ans2.size()) ans2.pb(Line[cnt-1].fi); cout<<ans1.size()<<endl; for(int i=0;i<ans1.size();i++) cout<<ans1[i]<<" "<<ans2[i]<<endl; return 0; }
Educational Codeforces Round 4 D. The Union of k-Segments 排序
原文：http://www.cnblogs.com/zxhl/p/5082484.html
