問題 B: Out-out-control cars

題目描述

Two out-of-control cars crashed within about a half-hour Wednesday afternoon on Deer Park Avenue. This accident alarmed the district government.
It jumpstarted a vibrant new technology to predict potential car accidents.
Engineers depicted a moving vehicle as a triangle with directional movement.
Three two dimeniaonal points (x1,y1),(x2,y2) and (x3,y3) restrict the span of a vehicle.
Its moverment is a uniform linear motion described by a vector (dx,dy).
That is say that after one second,the i-th endpoint of the emulational vehicle,the triangle,should be at (xi+dx,yi+dy).
The core function of this technology is simple.
For two given triangles,corresponding to two vehicles,predict that if they would collide in the near future.
Two triangles are considered collided,if they touched in some points or their intersection is not empty.
The first line of the input contains an integer tt specifying the number of test cases.
Each test case is consist of two lines and each line contains eight integers x1,y1,x2 ,y2,x3,y3 and dx,dy,to describe a vehicle and its movement.
The absolute value of each input number should be less than or equal to 10^9.
For each test case output the case number first. Then output YES if they would collide in the near future,or NO if they would never touch each other.

輸入

輸出

樣例輸入

30 1 2 1 1 3 1 0 9 2 10 4 8 4 -1 00 1 2 1 1 3 2 0 9 2 10 4 8 4 3 00 1 2 1 1 3 0 0 0 4 1 6 -1 6 1 -2

樣例輸出

Case #1: YES Case #2: NO Case #3: YES


#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <climits> #include <cstring> #include <string> #include <set> #include <bitset> #include <map> #include <queue> #include <stack> #include <vector> #include <cassert> #include <ctime> #define rep(i,m,n) for(i=m;i<=(int)n;i++) #define mod 100000007 #define inf 0x3f3f3f3f #define vi vector<int> #define pb push_back #define mp make_pair #define fi first #define se second #define ll long long #define pi acos(-1.0) #define pii pair<int,int> #define sys system("pause") #define ls rt<<1 #define rs rt<<1|1 #define all(x) x.begin(),x.end() using namespace std; struct Point{double x,y;}in[100]; //// 直線交點函數 int LineIntersect(Point A,Point B,Point C,Point D,double &x,double &y) {double a1,a2,b1,b2,c1,c2;double Delta , Delta_x , Delta_y;a1 = B.x - A.x; b1 = C.x - D.x; c1 = C.x - A.x;a2 = B.y - A.y; b2 = C.y - D.y; c2 = C.y - A.y;Delta=a1*b2-a2*b1; Delta_x=c1*b2-c2*b1;Delta_y=a1*c2-a2*c1;if(Delta) {x = A.x+a1*(Delta_x/Delta);y = A.y+a2*(Delta_x/Delta);return 1; //返回1: 表示兩條直線相交,且交點是(x , y) }else {if(!Delta_x && !Delta_y) return -1; //返回是-1: 表示兩條直線是重合關系else return 0; //返回0:表示兩條直線是平行不相交關系 } } bool panduan(Point a[],Point b[],double e,double f,int i,int j) {Point c;c.x=b[j].x+e;c.y=b[j].y+f;double x,y;int fan= LineIntersect(a[i],a[(i+1)%3],b[j],c,x,y);double miax,maax,miay,maay;if(a[i].x>a[(i+1)%3].x){maax=a[i].x;miax=a[(i+1)%3].x;}else{miax=a[i].x;maax=a[(i+1)%3].x;}if(a[i].y>a[(i+1)%3].y){maay=a[i].y;miay=a[(i+1)%3].y;}else{miay=a[i].y;maay=a[(i+1)%3].y;}double t;t=(x-b[j].x)/e;if(fan==1&&t>=0&&(x>=miax&&x<=maax)&&(y>=miay&&y<=maay))return true;return false; } int main() {Point a[5],b[5];int cas=1,t,i,j; scanf("%d",&t); double c,d,e,f;while(t--){int fl=0;rep(i,0,2)scanf("%lf %lf",&a[i].x,&a[i].y);scanf("%lf %lf",&c,&d);rep(i,0,2)scanf("%lf %lf",&b[i].x,&b[i].y);scanf("%lf %lf",&e,&f);e=e-c;f=f-d;rep(i,0,2){rep(j,0,2){if( panduan(a,b,e,f,i,j)){fl=1;break;}if(panduan(b,a,-e,-f,i,j)){fl=1;break;}}if(fl==1)break;}if(fl)printf("Case #%d: YES\n",cas++);elseprintf("Case #%d: NO\n",cas++);}return 0; }

?

轉載于:https://www.cnblogs.com/qksy/p/7521883.html

總結

以上是生活随笔為你收集整理的2017 ACM-ICPC 亚洲区(乌鲁木齐赛区)网络赛B: Out-out-control cars的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。