poj3304(是否存在一条直线与所有给出线段相交

  题意:给出n条线段,问你是否存在一条直线让他与所有线段相交。

  思路:枚举两条直线的起点和终点做一条直线,看他是否与所有线段相交。

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstring>
#include<queue>
#include<set>
#include<string>
#include<map>
#include <time.h>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = +;
const int sigma=;
const ll mod = ;
const int INF = 0x3f3f3f;
const db eps = 1e-;
struct point {
db x, y;
}s[maxn], e[maxn];
int n; db mul(point s, point e, point op) {
return (s.x-op.x)*(e.y-op.y)-(e.x-op.x)*(s.y-op.y);
}
bool seg(point p1, point p2) {
if (abs(p1.x-p2.x)<eps && abs(p1.y-p2.y)<eps) return ;
for (int i=; i<n; i++) {
if (mul(p1, p2, s[i])*mul(p1, p2, e[i])>eps) return ;
}
return ;
}
void solve() {
scanf("%d", &n);
for (int i=; i<n; i++) {
scanf("%lf%lf", &s[i].x, &s[i].y);
scanf("%lf%lf", &e[i].x, &e[i].y);
}
if (n<) {
puts("Yes!");
return ;
}
for (int i=; i<n; i++) {
for (int j=i+; j<n; j++) {
if (seg(s[i], s[j])||seg(s[i],e[j])
||seg(e[i], s[j])||seg(e[i], e[j])) {
puts("Yes!");
return;
}
}
}
puts("No!");
}
int main() {
int t = ;
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d", &t);
while(t--) {
solve();
}
return ;
}
上一篇:[学习]如何在c函数参数列表中输入多个值?


下一篇:Windows program design (Windows 程序设计提纲)第2章