Constraints

Time Limit: 3 secs, Memory Limit: 32 MB

Description

Irv Kenneth Diggit works for a company that excavates trenches, digs holes and generally tears up people‘s yards. Irv‘s job is to make sure that no underground pipe or cable is underneath where excavation is planned. He has several different maps, one for each utility company, showing where their conduits lie, and he needs to draw one large, consolidated map combining them all. One approach would be to simply draw each of the smaller maps one at a time onto the large map. However, this often wastes time, not to mention ink for the pen-plotter in the office, since in many cases portions of the conduits overlap with each other (albeit at different depths underground). What Irv wants is a way to determine the minimum number of line segments to draw given all the line segments from the separate maps.

Input

Input will consist of multiple input sets. Each set will start with a single line containing a positive integer n indicating the total number of line segments from all the smaller maps. Each of the next n lines will contain a description of one segment in the format x1 y1 x2 y2 where (x1,y1) are the coordinates of one endpoint and (x2,y2) are the coordinates of the other. Coordi- nate values are floating point values in the range 0... 1000 specified to at most two decimal places. The maximum number of line segments will be 10000 and all segments will have non-zero length. Following the last input set there will be a line containing a 0 indicating end of input; it should not be processed.

Output

For each input set, output on a single line the minimum number of line segments that need to be drawn on the larger, consolidated map.

Sample Input

3 1.0 10.0 3.0 14.0 0.0 0.0 20.0 20.0 10.0 28.0 2.0 12.0 2 0.0 0.0 1.0 1.0 1.0 1.0 2.15 2.15 2 0.0 0.0 1.0 1.0 1.0 1.0 2.15 2.16 0

分析：1.两点可以确定一条直线的方程。对于斜率存在的情况，k（斜率）、b（纵截距）和start、end（两点的横坐标）可以确定一条线段；对于斜率不存在的情况，k（可以表示为无穷）、b（

     两点共同的横坐标）和start、end（两点的纵坐标）可以确定一条线段。因此，一条线段可以由四个属性来确定。

        2.将所有线段按照以下规则来排序：
     对于两条线段，先比较k，k较小的在前；k相同时，比较b，b较小的在前；k、b都相同时，比较start，start较小的在前。

          经过排序后，如果两条线段有重合的部分，那么k、b相同，并且前一条线段的end要大于后一条线段的start。

          两条有重合部分的线段可以组成一条新线段。

 1 #include <iostream> 2 #include <algorithm> 3 #include <memory.h> 4 using namespace std; 5  6 #define EPS 1e-7 7  8 struct segment{ 9     double k;10     double b;11     double start;12     double end;13 };14 15 int dcmp(double a, double b){16     if(a - b < -EPS){17         return -1;18     } else if(a - b > EPS){19         return 1;20     } else {21         return 0;22     }23 }24 25 bool cmp(segment s1, segment s2){26     if(dcmp(s1.k, s2.k) != 0) {27         return dcmp(s1.k, s2.k) < 0;28     }29     if(dcmp(s1.b, s2.b) != 0){30         return dcmp(s1.b, s2.b) < 0;31     }32     return dcmp(s1.start, s2.start) < 0;33 }34 35 int main(){36     int n, i, j;37     segment seg[10000];38     while(cin >> n && n != 0){39         double x1, x2, y1, y2;40         int sum = n;41         for(i = 0; i < n; i++){42             cin >> x1 >> y1 >> x2 >> y2;43             if(dcmp(x1, x2) != 0){44                 seg[i].k = (y1 - y2)/(x1 - x2);45                 seg[i].b = y1 - seg[i].k * x1; 46                 seg[i].start = min(x1, x2);47                 seg[i].end = max(x1, x2);48             } else {49                 seg[i].k = 999999999;50                 seg[i].b = x1;51                 seg[i].start = min(y1, y2);52                 seg[i].end = max(y1, y2);53             }54         }55         sort(seg, seg+n, cmp);56         for(i = 0; i < n - 1; i++){57             if(dcmp(seg[i].k, seg[i+1].k) == 0 && dcmp(seg[i].b, seg[i+1].b) == 0 && dcmp(seg[i].end, seg[i+1].start) >= 0){58                 seg[i+1].end = max(seg[i].end, seg[i+1].end);59                 sum --;60             }61         }62         cout << sum << endl;63     }64     return 0;65 }

Sicily 1004. I Conduit!