| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
哪里错了啊,555555555555~~~~~~~·#include <stdio.h> #include <stdlib.h> #include <math.h> const double eps = 1e-8; const int Maxn = 105; struct TPoint { double x, y; }; struct TSegment { TPoint p1, p2; }; struct angle { double l, r; }; int parallel(TPoint s1, TPoint e1, TPoint s2, TPoint e2) { if(fabs((s1.y - e1.y) * (s2.x - e2.x) - (s2.y - e2.y) * (s1.x - e1.x)) < eps) return 1; else return 0; } double max(double x, double y) { //比较两个数的大小,返回大的数 if(x > y) return x; else return y; } double min(double x, double y) { //比较两个数的大小,返回小的数 if(x < y) return x; else return y; } double multi(TPoint p1, TPoint p2, TPoint p0) { return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y); } int isIntersected(TPoint s1, TPoint e1, TPoint s2, TPoint e2) { if( (max(s1.x, e1.x) >= min(s2.x, e2.x)) && (max(s2.x, e2.x) >= min(s1.x, e1.x)) && (max(s1.y, e1.y) >= min(s2.y, e2.y)) && (max(s2.y, e2.y) >= min(s1.y, e1.y)) && (multi(s2, e1, s1) * multi(e1, e2, s1) >= 0) && (multi(s1, e2, s2) * multi(e2, e1, s2) >= 0) ) return 1; return 0; } int get_angle(TSegment seg1, TSegment seg2, angle &a) { if(isIntersected(seg1.p1, seg1.p2, seg2.p1, seg2.p2)){ a.l = -1.0; a.r = 1.0; } else if(parallel(seg1.p1, seg1.p2, seg2.p1, seg2.p2)){ if(fabs(seg1.p1.x - seg1.p2.x) < eps) { // k = inf || k = -inf; a.l = 1.0; a.r = 1.0; return 1; } else if(fabs(seg1.p1.y - seg2.p2.y) < eps){ a.l = 0.0; a.r = 0.0; } } else { double k1, k2, tmpa, tmpb; if(isIntersected(seg1.p1, seg2.p1, seg1.p2, seg2.p2)){ //seg1.p1, seg2.p1 seg1.p2, seg2.p2 tmpa = seg1.p1.x - seg2.p1.x; tmpb = seg1.p1.y - seg2.p1.y; if(fabs(tmpb) < eps) k1 = 0.0; else if(fabs(tmpa) < eps) k1 = 1.0; else k1 = cos(atan(-tmpa / tmpb)); tmpa = seg1.p2.x - seg2.p2.x; tmpb = seg1.p2.y - seg2.p2.y; if(fabs(tmpb) < eps) k2 = 0.0; else if(fabs(tmpa) < eps) k2 = 1.0; else k2 = cos(atan(-tmpa / tmpb)); if(k1 < k2) a.l = k1, a.r = k2; else a.l = k2, a.r = k1; } else { //seg1.p1, seg2.p2 seg1.p2, seg2.p1 tmpa = seg1.p1.x - seg2.p2.x; tmpb = seg1.p1.y - seg2.p2.y; if(fabs(tmpb) < eps) k1 = 0.0; else if(fabs(tmpa) < eps) k1 = 1.0; else k1 = cos(atan(-tmpa / tmpb)); tmpa = seg1.p2.x - seg2.p1.x; tmpb = seg1.p2.y - seg2.p1.y; if(fabs(tmpb) < eps) k2 = 0.0; else if(fabs(tmpa) < eps) k2 = 1.0; else k2 = cos(atan(-tmpa / tmpb)); if(k1 < k2) a.l = k1, a.r = k2; else a.l = k2, a.r = k1; } } return 0; } int main() { int test, n, i, j, k, tag; TSegment seg[Maxn]; angle a, a1, b; scanf("%d", &test); while(test--){ scanf("%d", &n); for(i = 0;i < n;i++){ scanf("%lf%lf%lf%lf", &seg[i].p1.x, &seg[i].p1.y, &seg[i].p2.x, &seg[i].p2.y); } a1.l = -1.0; a1.r = 1.0; tag = 0; for(i = 0;i < n;i++){ for(j = i + 1;j < n;j++){ get_angle(seg[i], seg[j], a);//得到斜率角的范围 44 if(a1.l - a.r > 0 || a.l - a1.r > 0){ tag = 1; printf("No!\n"); break; } else { b.l = max(a1.l, a.l); b.r = min(a1.r, a.r); a1 = b; } } if(tag == 1) break; } if(tag == 0) printf("Yes!\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator