本文共 2519 字，大约阅读时间需要 8 分钟。
解法同POJ 1279 A一送一 缺点是还是O(n^2) ...nlogn的过几天补上...
/********************* Template ************************/#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define EPS 1e-8#define MAXN 10005#define MOD (int)1e9+7#define PI acos(-1.0)#define INF ((1LL)<<50)#define max(a,b) ((a) > (b) ? (a) : (b))#define min(a,b) ((a) < (b) ? (a) : (b))#define max3(a,b,c) (max(max(a,b),c))#define min3(a,b,c) (min(min(a,b),c))#define BUG cout<<"BUG! "< > 1)#define lowbit(a) (a & -a)#define FIN freopen("in.txt","r",stdin)#pragma comment (linker,"/STACK:102400000,102400000")// typedef long long LL;// typedef unsigned long long ULL;// typedef __int64 LL;// typedef unisigned __int64 ULL;// int gcd(int a,int b){ return b?gcd(b,a%b):a; }// int lcm(int a,int b){ return a*b/gcd(a,b); }/********************* F ************************/struct POINT{ double x,y; POINT(double _x = 0, double _y = 0):x(_x),y(_y){}}p[MAXN],q[MAXN],t[MAXN];int n;struct LINE{ double a,b,c; POINT A,B; LINE(POINT _a, POINT _b):A(_a),B(_b){ a=B.y-A.y; b=A.x-B.x; c=B.x*A.y-A.x*B.y; }};double multiply(POINT sp,POINT ep,POINT op){ //叉积 左+ 右- return (sp.x-op.x) * (ep.y-op.y) - (ep.x-op.x) * (sp.y-op.y);}POINT Intersection(LINE a,LINE b){ //直线交点 double u = fabs(b.A.x * a.a + b.A.y * a.b + a.c); double v = fabs(b.B.x * a.a + b.B.y * a.b + a.c); POINT t; t.x = (b.A.x * v + b.B.x * u) / (u + v); t.y = (b.A.y * v + b.B.y * u) / (u + v); return t;}int main(){ //freopen("in.txt","r",stdin); //freopen("outm.txt","w",stdout); int ct = 1; while(cin>>n && n){ for(int i = 0 ; i < n ; i++) scanf("%lf%lf",&p[i].x,&p[i].y); //暴力对每一个向量作半平面交 ...即将右侧的点和与其他直线的交点加入集合 for(int i = 0 ; i < n ; i++) q[i] = p[i]; int cnt = n; for(int i = 0 ; i < n ; i++){ int c = 0; for(int j = 0 ; j < cnt ; j++){ //点在右侧 if(multiply(p[i],p[(i+1)%n],q[j]) <= EPS) { t[c++] = q[j]; }else { //点在左侧,但是前后线段和该直线有交点 //这个顺序不要写反,否则不是顺时针会WA if(multiply(p[i],p[(i+1)%n],q[(j-1+cnt)%cnt]) < -EPS){ t[c++] = Intersection(LINE(p[i],p[(i+1)%n]) , LINE(q[j],q[(j-1+cnt)%cnt])); } if(multiply(p[i],p[(i+1)%n],q[(j+1)%cnt]) < -EPS){ t[c++] = Intersection(LINE(p[i],p[(i+1)%n]) , LINE(q[j],q[(j+1)%cnt])); } } } for(int j = 0 ; j < c ; j++) {q[j] = t[j];} cnt = c; } cout<<"Floor #"< <
转载于:https://www.cnblogs.com/Felix-F/p/3258807.html