POJ 1765 - November Rain

http://poj.org/problem?id=1765

Contemporary buildings can have very complicated roofs. If we take a vertical section of such a roof it results in a number of sloping segments. When it is raining the drops are falling down on the roof straight from the sky above. Some segments are completely exposed to the rain but there may be some segments partially or even completely shielded by other segments. All the water falling onto a segment as a stream straight down from the lower end of the segment on the ground or possibly onto some other segment. In particular, if a stream of water is falling on an end of a segment then we consider it to be collected by this segment.

For the purpose of designing a piping system it is desired to compute how much water is down from each segment of the roof. To be prepared for a heavy November rain you should count one liter of rain water falling on a meter of the horizontal plane during one second.

Task
Write a program that:

reads the description of a roof,
computes the amount of water down in one second from each segment of the roof,
writes the results.

Input

The first line of the input contains one integer n (1 <= n < = 40000) being the number of segments of the roof. Each of the next n lines describes one segment of the roof and contains four integers x1, y1, x2, y2 (0 <= x1, y1, x2, y2 < = 1000000, x1 < x2, y1<>y2) separated by single spaces. Integers x1, y1 are respectively the horizontal position and the height of the left end of the segment. Integers x2, y2 are respectively the horizontal position and the height of the right end of the segment. The segments don't have common points and there are no horizontal segments. You can also assume that there are at most 25 segments placed above any point on the ground level.

Output

The output consists of n lines. The i-th line should contain the amount of water (in liters) down from the i-th segment of the roof in one second.

Sample Input

6
13 7 15 6
3 8 7 7
1 7 5 6
5 5 9 3
6 3 8 2
9 6 12 8

Sample Output

2
4
2
11
0
3

http://www.voidcn.com/article/p-zgpuhifb-qy.html

题意：有很多倾斜的屋檐，这些屋檐不会相交，每个屋檐会接收雨水，并从较低短流到另一个在它下面的屋檐，要求每秒钟每个屋檐流下的水量，最多有25个屋檐在同一垂直线上

分析：这题直接假想有一条垂直的扫描线从最左端开始，向右扫描，每个事件点为屋檐的端点，每次如果为屋檐的左端点，就加入队列，如果是右端点，就从队列中删掉，队列里的屋檐，按低到高排序，通过判断队列中屋檐的相对位置，是否有水流下，是否被覆盖。。。等等就可以算出每个屋檐自己接到的雨水，和每个屋檐的关系，然后根据拓扑排序，把在高处的雨水流到较低的屋檐就行。。。

struct point
{
    int x,y,id,fl;
}g[mm];
double a[mm],b[mm],c[mm];
int head[mm],ver[mn],next[mn];
int sum[mm],cov[mm],q[mm],h[mm],s[mm],d[mm],flag[mm],down[mm];
int i,j,k,l,r,x1,x2,y1,y2,n,m,edge;
bool cmp(point a,point b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
void addedge(int u,int v)
{
    ver[edge]=v,++d[v],next[edge]=head[u],head[u]=edge++;
}
void add(point p)
{
    down[p.id]=p.fl;
    if(!flag[p.id])
    {
        flag[p.id]=1;
        int i=r++;
        while(i>0&&(-a[q[i]]*p.x-c[q[i]])/b[q[i]]>p.y)q[i+1]=q[i],--i;
        q[++i]=p.id;
    }
    else flag[p.id]=2;
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    while(scanf("%d",&n)!=-1)
    {
        for(m=0,i=1;i<=n;++i)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            a[i]=y1-y2,b[i]=x2-x1,c[i]=x1*y2-x2*y1;
            s[i]=min(x1,x2);
            h[i]=min(y1,y2);
            j=y1<y2;
            g[m].x=x1,g[m].y=y1,g[m].fl=j,g[m].id=i,m++;
            g[m].x=x2,g[m].y=y2,g[m].fl=!j,g[m].id=i,m++;
            d[i]=cov[i]=flag[i]=sum[i]=0;
            head[i]=-1;
        }
        sort(g,g+m,cmp);
        r=edge=i=0;
        while(i<m)
        {
            x1=g[i].x;
            add(g[i++]);
            while(i<m&&g[i].x==x1)add(g[i++]);
            for(j=1;j<=r;++j)
            {
                if(!cov[q[j]])sum[q[j]]+=x1-s[q[j]];
                s[q[j]]=x1;
            }
           for(j=1;j<r;++j)
                if(down[q[j+1]])addedge(q[j+1],q[j]);
            for(k=0,j=1;j<=r;++j)
                if(flag[q[j]]<2)q[++k]=q[j];
            for(r=k,j=1;j<=r;++j)down[q[j]]=0,cov[q[j]]=1;
            cov[q[r]]=0;
        }
        for(r=0,i=1;i<=n;++i)
            if(!d[i])q[r++]=i;
        for(l=0;l<r;++l)
            for(i=head[q[l]];i>=0;i=next[i])
            {
                sum[ver[i]]+=sum[q[l]];
                if(--d[ver[i]]==0)q[r++]=ver[i];
            }
        for(i=1;i<=n;++i)printf("%d\n",sum[i]);
    }
    return 0;
}

Convex hull - sweep line

https://www.topcoder.com/community/competitive-programming/tutorials/line-sweep-algorithms/

The convex hull of a set of points is the smallest convex polygon that surrounds the entire set, and has a number of practical applications. An efficient method that is often used in challenges is the Graham scan [2], which requires a sort by angle. This isn’t as easy as it looks at first, since computing the actual angles is expensive and introduces problems with numeric error. A simpler yet equally efficient algorithm is due to Andrew [1], and requires only a sort by X for a line sweep (although Andrew’s original paper sorts by Y and has a few optimizations I won’t discuss here).

Andrew’s algorithm splits the convex hull into two parts, the upper and lower hull. Usually these meet at the ends, but if more than one points has minimal (or maximal) X coordinate, then they are joined by a vertical line segment. We’ll describe just how to construct the upper hull; the lower hull can be constructed in similar fashion, and in fact can be built in the same loop.

To build the upper hull, we start with the point with minimal X coordinate, breaking ties by taking the largest Y coordinate. After this, points are added in order of X coordinate (always taking the largest Y value when multiple points have the same X value). Of course, sometimes this will cause the hull to become concave instead of convex:

The black path shows the current hull. After adding point 7, we check whether the last triangle (5, 6, 7) is convex. In this case it isn’t, so we delete the second-last point, namely 6. The process is repeated until a convex triangle is found. In this case we also examine (4, 5, 7) and delete 5 before examining (1, 4, 7) and finding that it is convex, before proceeding to the next point. This is essentially the same procedure that is used in the Graham scan, but proceeding in order of X coordinate rather than in order of the angle made with the starting point. It may at first appear that this process is O(N2) because of the inner backtracking loop, but since no point can be deleted more than once it is in fact O(N). The algorithm over-all is O(N log N), because the points must initially be sorted by X coordinate.

https://www.hackerearth.com/practice/math/geometry/line-sweep-technique/tutorial/
Let S be a set of points. Then, convex hull is the smallest convex polygon which covers all the points of S.
There exists an efficient algorithm for convex hull (Graham Scan) but here we discuss the same idea except for we sort on the basis of x coordinates instead of angle.
The pseudo code for the algorithm is:

Sort the points of P by x-coordinate (in case of a tie, sort by y-coordinate).

Initialize U and L as empty lists.
The lists will hold the vertices of upper and lower hulls respectively.

for i = 1, 2, ..., n:
    while L contains at least two points and the sequence of last two points
            of L and the point P[i] does not make a counter-clockwise turn:
        remove the last point from L
    append P[i] to L

for i = n, n-1, ..., 1:
    while U contains at least two points and the sequence of last two points
            of U and the point P[i] does not make a counter-clockwise turn:
        remove the last point from U
    append P[i] to U

Remove the last point of each list (it's the same as the first point of the other list).
Concatenate L and U to obtain the convex hull of P.
Points in the result will be listed in counter-clockwise order.

C++ implementation of the above algorithm is as follows:

struct Point {
        double x, y;
};
bool compare(Point a,Point b)
{
        return a.x<b.x || (a.x==b.x && a.y<b.y);
}
//Returns positive value if B lies to the left of OA, negative if B lies to the right of OA, 0 if collinear
double cross(const Point &O, const Point &A, const Point &B)
{
        return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
//Returns a list of points on the convex hull
vector<Point> convex_hull(vector<Point> P)
{
        int n = P.size(), k = 0;
        vector<Point> H(2*n);
        sort(P.begin(), P.end(),compare);
        // Build lower hull
        for (int i = 0; i < n; ++i) {
                while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
                H[k++] = P[i];
        }

        // Build upper hull
        //i starts from n-2 because n-1 is the point which both hulls will have in common
        //t=k+1 so that the upper hull has atleast two points to begin with
        for (int i = n-2, t = k+1; i >= 0; i--) {
                while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
                H[k++] = P[i];
        }
        //the last point of upper hull is same with the fist point of the lower hull
        H.resize(k-1);
        return H;
}

$<br>$

HDU 1255 - 覆盖的面积

http://acm.hdu.edu.cn/showproblem.php?pid=1255

给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.

 

Input

输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N<=1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表平面上的一个矩形的左上角坐标和右下角坐标,矩形的上下边和X轴平行,左右边和Y轴平行.坐标的范围从0到100000.

注意:本题的输入数据较多,推荐使用scanf读入数据.

 

Output

对于每组测试数据,请计算出被这些矩形覆盖过至少两次的区域的面积.结果保留两位小数.

 

Sample Input

2
5
1 1 4 2
1 3 3 7
2 1.5 5 4.5
3.5 1.25 7.5 4
6 3 10 7
3
0 0 1 1
1 0 2 1
2 0 3 1

 

Sample Output

7.63
0.00

https://blog.csdn.net/Mr_Treeeee/article/details/76039113

cnt[x]即代表x区间的线段存在了几次，>=2即是重合了一次或多次。 用法和HDU 1542相同。

然后每次计算就询问一次。乘以高度就行。

LeetCode 759 - Employee Free Time

http://www.cnblogs.com/grandyang/p/8552586.html

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation:
There are a total of three employees, and all common
free time intervals would be [-inf, 1], [3, 4], [10, inf].
We discard any intervals that contain inf as they aren't finite.

Example 2:

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined.)

Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.

Note:

1. schedule and schedule[i] are lists with lengths in range [1, 50].
2. 0 <= schedule[i].start < schedule[i].end <= 10^8.

题目大意：给你每个员工的日历，让你找出所有员工都有空的时间段。

X. PriorityQueue:
Time Complexity: O(nlogk). k是employee的个数, schedule.size(). n是一共有多少interval.
http://hehejun.blogspot.com/2018/02/leetcodeemployee-free-time.html
此外我们用merge k sorted lists的解法也可以
https://www.cnblogs.com/Dylan-Java-NYC/p/9399311.html

k条已经排好序的链表. 利用minHeap进行merge. 

先把每个表头放在minHeap中. minHeap按照指向的Interval start排序.

poll出来的就是当前最小start的interval. 如果标记的时间比这个interval的start还小就说明出现了断裂也就是空余时间. 

把标记时间增大到这个interval的end, 并且把这个interval所在链表的后一位加入minHeap中.

Time Complexity: O(nlogk). k是employee的个数, schedule.size(). n是一共有多少interval.

Space: O(k).

11     public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
12         List<Interval> res = new ArrayList<Interval>();
13         PriorityQueue<Node> minHeap = new PriorityQueue<Node>((a,b) -> 
14                                             schedule.get(a.employee).get(a.index).start - schedule.get(b.employee).get(b.index).start);
15         
16         int start = Integer.MAX_VALUE;
17         for(int i = 0; i<schedule.size(); i++){
18             minHeap.add(new Node(i, 0));
19             start = Math.min(start, schedule.get(i).get(0).start);
20         }
21         
22         while(!minHeap.isEmpty()){
23             Node cur = minHeap.poll();
24             if(start < schedule.get(cur.employee).get(cur.index).start){
25                 res.add(new Interval(start, schedule.get(cur.employee).get(cur.index).start));
26             }
27             
28             start = Math.max(start, schedule.get(cur.employee).get(cur.index).end);
29             cur.index++;
30             if(cur.index < schedule.get(cur.employee).size()){
31                 minHeap.add(cur);
32             }
33         }
34         
35         return res;
36     }
39 class Node{
40     int employee;
41     int index;
42     public Node(int employee, int index){
43         this.employee = employee;
44         this.index = index;
45     }
46 }

https://blog.csdn.net/zjucor/article/details/79007431
合并所有的interval，找到空隙的，可以对所有的interval进行一遍排序（按照interval.start，因为合并要按照start的顺序来才是对的），用优先队列可以进一步简化时间复杂度，省去了整体排序的时间

  public List<Interval> employeeFreeTime(final List<List<Interval>> avails) {

    PriorityQueue<int[]> pq = new PriorityQueue<int[]>(50, new Comparator<int[]>() {

      @Override

      public int compare(int[] a1, int[] a2) {

        return avails.get(a1[0]).get(a1[1]).start - avails.get(a2[0]).get(a2[1]).start;

      }

    });

    Stack<Interval> st = new Stack<Interval>();

    for (int i = 0; i < avails.size(); i++)

      pq.add(new int[] { i, 0 });

    while (!pq.isEmpty()) {

      int[] tt = pq.remove();

      if (tt[1] + 1 < avails.get(tt[0]).size())

        pq.add(new int[] { tt[0], tt[1] + 1 });

      Interval t = avails.get(tt[0]).get(tt[1]);

      if (st.isEmpty()) {

        st.add(t);

      } else {

        Interval top = st.pop();

        if (top.end >= t.start) {

          st.push(new Interval(top.start, Math.max(top.end, t.end)));

        } else {

          st.push(top);

          st.push(t);

        }

      }

    }

    List<Interval> ret = new ArrayList<Interval>();

    LinkedList<Interval> t = new LinkedList<Interval>();

    while (!st.isEmpty())

      t.add(0, st.pop());

    for (int i = 0; i < t.size() - 1; i++)

      ret.add(new Interval(t.get(i).end, t.get(i + 1).start));

    return ret;

  }

X. TreeMap: O(nlogn)

我们再来看一种解法，这种解法挺巧妙的，我们使用TreeMap建立一个位置和其出现次数之间的映射，对于起始位置，进行正累加，对于结束位置，进行负累加。由于TreeMap具有自动排序的功能，所以我们进行遍历的时候，就是从小到大进行遍历的。定义一个变量cnt，初始化为0，我们对于每个遍历到的数，都加上其在TreeMap中的映射值，即该数字出现的次数，起始位置的话就会加正数，结束位置就是加负数。开始的时候，第一个数字一定是个起始位置，那么cnt就是正数，那么接下来cnt就有可能加上正数，或者减去一个负数，我们想，如果第一个区间和第二个区间没有交集的话，那么接下来遇到的数字就是第一个区间的结束位置，所以会减去1，这样此时cnt就为0了，这说明一定会有中间区域存在，所以我们首先把第一个区间当前起始位置，结束位置暂时放上0，组成一个区间放到结果res中，这样我们在遍历到下一个区间的时候更新结果res中最后一个区间的结束位置。语言描述难免太干巴巴的，我们拿题目中的例1来说明，建立好的TreeMap如下所示：

1 -> 2
2 -> -1
3 -> -1
4 -> 1
5 -> 1
6 -> -1
10 -> -1

那么开始遍历这所有的映射对，cnt首先为2，然后往后遍历下一个映射对2 -> -1，此时cnt为1了，不进行其他操作，再往下遍历，下一个映射对3 -> -1，此时cnt为0了，说明后面将会出现断层了，我们将(3, 0)先存入结果res中。然后遍历到4 -> 1时，cnt为1，此时将结果res中的(3, 0)更新为 (3, 4)。然后到5 -> 1，此时cnt为2，不进行其他操作，然后到6 -> -1，此时cnt为1，不进行其他操作，然后到10 -> -1，此时cnt为0，将(10, 0)加入结果res中。由于后面再没有任何区间了，所以res最后一个区间不会再被更新了，我们应该将其移出结果res，因为题目中限定了区间不能为无穷，参见代码如下：

    vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {
        vector<Interval> res;
        map<int, int> m;
        int cnt = 0;
        for (auto employee : schedule) {
            for (Interval i : employee) {
                ++m[i.start];
                --m[i.end];
            }
        }
        for (auto a : m) {
            cnt += a.second;
            if (!cnt) res.push_back(Interval(a.first, 0));
            if (cnt && !res.empty() && !res.back().end) res.back().end = a.first;
        }
        if (!res.empty()) res.pop_back();
        return res;
    }

X. Sort Intervals

    vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {

      vector<Interval> all;

      for (const auto intervals : schedule)

        all.insert(all.end(), intervals.begin(), intervals.end());

      std::sort(all.begin(), all.end(),

                [](const Interval& a, const Interval& b){

                  return a.start < b.start;

                });

      vector<Interval> ans;

      int end = all.front().end;

      for (const Interval& busy : all) {

        if (busy.start > end)

          ans.emplace_back(end, busy.start);  

        end = max(end, busy.end);

      }

      return ans;

    }

这道题和之前那道Merge Intervals基本没有太大的区别，那道题是求合并后的区间，这道题求合并后区间中间不相连的区间。那么只要我们合并好了区间，就很容易做了。那么我么首先应该给所有的区间排个序，按照起始位置从小到大来排。因为我们总不可能一会处理前面的，一会处理后面的区间。排好序以后，我们先取出第一个区间赋给t，然后开始遍历所有的区间内所有的区间，如果t的结束位置小于当前遍历到的区间i的起始位置，说明二者没有交集，那么把不相交的部分加入结果res中，然后把当前区间i赋值给t；否则如果区间t和区间i有交集，那么我们更新t的结束位置为二者中的较大值，因为按顺序遍历区间的时候，区间t的结束位置是比较的基准，越大越容易和后面的区间进行合并

    vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {
        vector<Interval> res, v;
        for (auto a : schedule) {
            v.insert(v.end(), a.begin(), a.end());
        }
        sort(v.begin(), v.end(), [](Interval &a, Interval &b) {return a.start < b.start;});
        Interval t = v[0];
        for (Interval i : v) {
            if (t.end < i.start) {
                res.push_back(Interval(t.end, i.start));
                t = i;
            } else {
                t = (t.end < i.end) ? i : t;
            }
        }
        return res;
    }

https://segmentfault.com/a/1190000016324456

    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        List<Interval> res = new ArrayList<>();
        List<Interval> times = new ArrayList<>();
        for (List<Interval> list: schedule) {
            times.addAll(list);
        }
        Collections.sort(times, ((i1, i2)->i1.start-i2.start));
        Interval pre = times.get(0);
        for (int i = 1; i < times.size(); i++) {
            Interval cur = times.get(i);
            if (cur.start <= pre.end) {
                pre.end = cur.end > pre.end ? cur.end : pre.end;
            } else {
                res.add(new Interval(pre.end, cur.start));
                pre = cur;
            }    
        }
        return res;
    }

X. https://blog.csdn.net/magicbean2/article/details/79569830

我们首先将所有员工的工作时段进行合并。然后从合并后的intervals中找出有限的空余时段即可。整个算法的时间复杂度是O(nlogn)，空间复杂度是O(n)，其中n是所有员工的工作时段的总数。

    vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {

        vector<Interval> intervals, result, ans;

        for (int i = 0; i < schedule.size(); ++i) {

            for (int j = 0; j < schedule[i].size(); ++j) {

                intervals.push_back(schedule[i][j]);

            }

        }

        sort(intervals.begin(), intervals.end(), [](const Interval &a, const Interval &b) {

            return a.start < b.start || (a.start == b.start && a.end < b.end); });

        result.push_back(intervals[0]);

        for (int i = 1; i < intervals.size(); ++i) {

            if (intervals[i].start <= result.back().end) {

                result.back().end = max(result.back().end, intervals[i].end);

            }

            else {

                result.push_back(intervals[i]);

            }

        }

        for (int i = 0; i + 1 < result.size(); ++i) {

            if (result[i].end < result[i + 1].start) {

                ans.push_back(Interval(result[i].end, result[i + 1].start));

            }

        }

        return ans;

    }

X. Videos

花花酱 LeetCode 759. Employee Free Time - 刷题找工作 EP 154