| ||||||||||
| 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 | |||||||||
破100了纪念一下吧这题还是挺有收获的。
要注意线段在矩形内的情况,
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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator