Uva 191 Intersection

題目來源：https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=127

胡言亂語：

剛看到這一題的時候，就想說，可能先要判斷線段和矩形的四個邊有沒有交點，在來判斷線段是否在矩形內，但想一想，會不會更簡單啊？？

突然想到，那把線段切成很多小點，判斷每個點是否在矩形內不就好了？

線段方程式：ax+by = c  ==>千萬不要用這個，因為這樣就會有三個變數

                        y  = ax+b  ==>這樣只剩兩個變數而已

因此我已x為變化基準，計算x' = x+0.5為間距的點是否在矩形內，但這樣WA了。

測了一下，發現兩個錯誤

(1)  若為垂直線則無斜率，需要另外處理

(2)  x' = x+0.1  之前間距(0.5)太大，會有漏掉的點

修改後終於AC了  ^___^

程式碼：

	#include<iostream>
	#include<algorithm>
	#include<cstdio>
	#include<cstdlib>
	using namespace std;
	struct Point {
	double x,y;
	};
	Point p1,p2;//設定矩形的左下和右下
	double a,b;//存入線段方程式的係數
	//判斷是否為矩形內
	//float不可能完全相同，有一定的誤差在
	bool Test_rectangles(Point t){
	if(t.x>p1.x-0.00001 && t.x<p2.x+0.00001 && t.y<p2.y+0.00001 && t.y>p1.y-0.0001)
	return true;
	else return false;
	}
	//計算線段的方程式
	void get_polynominal(Point m,Point n){
	a = (m.y-n.y)/(m.x-n.x);
	b = m.y-(a*m.x);
	}
	int main(){
	int N;
	bool tag;
	double u;
	scanf("%d",&N);
	Point line_point1,linr_point2,temp;
	while(N--){
	tag = false;
	scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&line_point1.x,&line_point1.y,&linr_point2.x,&linr_point2.y,&p1.x,&p1.y,&p2.x,&p2.y);
	//p1代表左下 p2代表右上
	if(p1.x>p2.x) swap(p1.x,p2.x);
	if(p1.y>p2.y) swap(p1.y,p2.y);
	//若為垂直線的情況，因為垂直線無斜率
	if(line_point1.x==linr_point2.x){
	if(line_point1.y>linr_point2.y) swap(line_point1.y,linr_point2.y);
	for(double i=line_point1.y;i<=linr_point2.y+0.0001;i+=0.003){
	temp.x = line_point1.x;
	temp.y = i;
	if(Test_rectangles(temp)){
	tag = true;
	printf("T\n");
	break;
	}
	}
	if(!tag) printf("F\n");
	continue;
	}
	//非垂直線情況
	if(line_point1.x> linr_point2.x) {
	temp = line_point1 ;
	line_point1 = linr_point2;
	linr_point2 = temp;
	}
	//取得斜率和係數 y=ax+b
	get_polynominal(line_point1,linr_point2);
	//注意：抓的點的密度要夠，不然會有誤差
	for(double i=line_point1.x;i<=linr_point2.x+0.0001;i+=0.05){
	temp.x = i;
	temp.y = a*i+b;
	if(Test_rectangles(temp)){
	tag = true;
	printf("T\n");
	break;
	}
	}
	if(!tag) printf("F\n");
	}
	}

view raw uva_191.cpp hosted with ❤ by GitHub