大致题意：
1e3 个线段，画在一张纸上，，求可以看成多少个线段，（ 两个线段部分重叠，或收尾相接将看成一个线段）
思路：
在同一一条直线上的两条线段: 他们斜率相等，他们在Y轴或X轴上的投影点相等。然后根据这两个排下序就可以搞出来了。
这题卡精度，要用到eps
//#pragma comment(linker, "/STACK:1024000000,1024000000")#include <iostream>#include <cstring>#include <cmath>#include <queue>#include <stack>#include <map>#include <set>#include <string>#include <vector>#include <cstdio>#include <ctime>#include <bitset>#include <algorithm>#define SZ(x) ((int)(x).size())#define ALL(v) (v).begin(), (v).end()#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)#define reveach(i, v) for (__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++ i)#define REP(i,n) for ( int i=1; i<=int(n); i++ )#define rep(i,n) for ( int i=0; i< int(n); i++ )using namespace std;typedef long long ll;#define X first#define Y secondtypedef pair<double,double> pii;template <class T>inline bool RD(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c – '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c – '0');ret *= sgn;return 1;}template <class T>inline void PT(T x) {if (x < 0) {putchar('-');x = -x;}if (x > 9) PT(x / 10);putchar(x % 10 + '0');}const int N = 1e4+100;const double inf = 1e30;const double eps = 1e-6;int n;struct node{pii u,v;double k,p;}all[N];bool d1(double x,double y) { return x > y + eps;} // x > ybool d2(double x,double y) { return x < y – eps;} // x < ybool d3(double x,double y) { return x > y – eps;} // x >= ybool d4(double x,double y) { return x < y + eps;}// x <= ybool dd(double x,double y) { return fabs( x – y ) < eps;} // x == ybool cmp(const node& a, const node& b) {if( dd(a.k , b.k) ) {if( dd( a.p , b.p ) ) {if( dd( a.u.X , b.u.X ) ) return d2( a.u.Y , b.u.Y);return d2( a.u.X , b.u.X );}return d2( a.p, b.p) ;}return d2(a.k , b.k) ;}int main(){while( scanf("%d",&n) && n){REP(i,n){scanf("%lf%lf%lf%lf",&all[i].u.X, &all[i].u.Y, &all[i].v.X, &all[i].v.Y);if( d1( all[i].u.X , all[i].v.X ) ) swap(all[i].u, all[i].v);if( dd( all[i].u.X , all[i].v.X ) ) {if( d1( all[i].u.Y , all[i].v.Y ) ) swap(all[i].u, all[i].v);all[i].k = inf;all[i].p = all[i].u.X;}else {all[i].k = ( ( all[i].u.Y – all[i].v.Y )/( all[i].u.X – all[i].v.X ) );all[i].p = all[i].u.Y – all[i].k * all[i].u.X;}}sort(all+1,all+1+n,cmp);all[0].k = all[0].p = -inf;int ans = 0, pos = 0;double bord;REP(i,n){if( dd( all[i].k , inf) ) { pos = i; break; }if( dd( all[i].k , all[i-1].k ) == false || dd( all[i].p , all[i-1].p ) == false ){ans ++;bord = all[i].v.X;}else{if( d1( all[i].u.X , bord ) ) ans ++;bord = max( bord, all[i].v.X );}}if( pos ) {ans ++;bord = all[pos].v.Y;for(int i = pos+1; i <= n; i ++){if( dd( all[i].p , all[i-1].p ) == false ) ans ++, bord = all[i].v.Y;else{if( d1( all[i].u.Y , bord ) ) ans ++;bord = max( bord, all[i].v.Y );}}}PT(ans),puts("");}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。
