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