Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

哪里错了啊,555555555555~~~~~~~·

Posted by chenhaifeng at 2007-09-11 19:21:31 on Problem 3304
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator