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

破100了纪念一下吧

Posted by cep_cep at 2009-09-01 21:56:16 on Problem 1410
这题还是挺有收获的。

要注意线段在矩形内的情况,
WA了几次才想到!

一定要认真读题!
贴下代码吧:
#include <stdio.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a>b?b:a)

struct Point{
	int x,y;
};
struct Rectangle{
	Point p1,p2;
};

inline int mult(Point p0,Point p1,Point p2){
	return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

bool onSeg(Point p0,Point p1,Point p2){//p0是否在线段p1p2上
	return mult(p0,p1,p2)==0&&p0.x>=min(p1.x,p2.x)&&p0.x<=max(p1.x,p2.x)&&p0.y>=min(p1.y,p2.y)&&p0.y<=max(p1.y,p2.y);
}

bool inter(Point p1,Point p2,Point p3,Point p4){//矩形的一边是否和线段相交
	if(onSeg(p1,p3,p4)||onSeg(p2,p3,p4)||onSeg(p3,p1,p2)||onSeg(p4,p1,p2))
		return true;
	if(mult(p1,p2,p3)*mult(p1,p2,p4)<0&&mult(p3,p4,p1)*mult(p3,p4,p2)<0)
		return true;
	return false;
}

inline bool check(Point p1,Point p2,Point p3,Point p4){//线段是否在矩形内
	if(max(p1.x,p2.x)<=max(p3.x,p4.x)&&min(p1.x,p2.x)>min(p3.x,p4.x)&&max(p1.y,p2.y)<max(p3.y,p4.y)&&min(p1.y,p2.y)>min(p3.y,p4.y))
		return true;
	return false;
}

int main(){

	int n;
	Rectangle R;
	Point p,pp,t;

	scanf("%d",&n);
	while(n-->0){
		scanf("%d%d%d%d%d%d%d%d",&p.x,&p.y,&pp.x,&pp.y,&R.p1.x,&R.p1.y,&R.p2.x,&R.p2.y);

		if(check(p,pp,R.p1,R.p2)){
			printf("T\n");
			continue;
		}

		t.x=R.p1.x;
		t.y=R.p2.y;
		if(inter(p,pp,t,R.p1)||inter(p,pp,t,R.p2)){
			printf("T\n");
			continue;
		}

		t.x=R.p2.x;
		t.y=R.p1.y;
		if(inter(p,pp,t,R.p1)||inter(p,pp,t,R.p2)){
			printf("T\n");
			continue;
		}

		printf("F\n");
	}
}

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