// 线段相交 poj 1066
// 思路:直接枚举每个端点和终点连成线段,判断和剩下的线段相交个数 // #include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
#define LL long long
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const LL MOD =100000000LL;
const int N =;
#define clc(a,b) memset(a,b,sizeof(a))
const double eps = 1e-;
void fre() {freopen("in.txt","r",stdin);}
void freout() {freopen("out.txt","w",stdout);}
inline int read() {int x=,f=;char ch=getchar();while(ch>''||ch<'') {if(ch=='-') f=-; ch=getchar();}while(ch>=''&&ch<='') {x=x*+ch-'';ch=getchar();}return x*f;} int sgn(double x){
if(fabs(x) < eps)return ;
if(x < )return -;
else return ;
}
struct Point{
double x,y;
Point(){}
Point(double _x,double _y){
x = _x;y = _y;
}
Point operator -(const Point &b)const{
return Point(x - b.x,y - b.y);
}
double operator ^(const Point &b)const{
return x*b.y - y*b.x;
}
double operator *(const Point &b)const{
return x*b.x + y*b.y;
}
}; struct Line{
Point s,e;
int inx;
Line(){}
Line(Point _s,Point _e){
s=_s;e=_e;
}
}; Line line[N];
bool inter(Line l1,Line l2){
return
max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) &&
max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) &&
max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) &&
max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) &&
sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s)) <= &&
sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s)) <= ;
} vector<Line> list;
bool cmp(Line l1,Line l2){
return l1.inx<l2.inx;
} Point p[];
int main(){
int n;
while(~scanf("%d",&n)){
for(int i=;i<=n;i++){
double x1,y1,x2,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
line[i]=Line(Point(x1,y1),Point(x2,y2));
p[i*-]=Point(x1,y1);
p[i*]=Point(x2,y2);
}
double x1,y1;
scanf("%lf%lf",&x1,&y1);
Point s=Point(x1,y1);
int ans=inf;
for(int i=;i<=*n;i++){
int tem=;
for(int j=;j<=n;j++){
if(inter(Line(s,p[i]),line[j]))
tem++;
}
ans=min(ans,tem);
} Point p1;
p1=Point(,);
int tem=;
for(int i=;i<=n;i++){
if(inter(Line(s,p1),line[i]))
tem++;
}
ans=min(ans,tem+); p1=Point(,);
tem=;
for(int i=;i<=n;i++){
if(inter(Line(s,p1),line[i]))
tem++;
}
ans=min(ans,tem+); p1=Point(,);
tem=;
for(int i=;i<=n;i++){
if(inter(Line(s,p1),line[i]))
tem++;
}
ans=min(ans,tem+); p1=Point(,);
tem=;
for(int i=;i<=n;i++){
if(inter(Line(s,p1),line[i]))
tem++;
}
ans=min(ans,tem+);
printf("Number of doors = ");
printf("%d\n",ans);
}
return ;
}

最新文章

  1. HackerNews——《Pokemon Go玩家存在巨大的安全风险》
  2. 堆排序分析及php实现
  3. ASP.NET的一般处理程序对图片文件的基本操作
  4. php防止刷新(流量攻击)的一段代码
  5. C++编译器默默编写并调用哪些函数
  6. 被误解的 MVC 和被神化的 MVVM
  7. Failed to collect certificates from /data/app/vmdl201020547.tmp/base.apk: META-INF/CERT.SF indicates /data/app/vmdl201020547.tmp/base.apk is signed using APK Signature Scheme v2, but no such signature
  8. 寻找数列中第k大的数算法分析
  9. cocos2d-x 截取屏幕可见区域
  10. USACO Section 1.3 Mixing Milk 解题报告
  11. 【开发技术】对文件内容进行加密-java
  12. mysql 2pc理解
  13. 我的数据,我做主——RecoveryManager Plus
  14. 上这个资源网站,让你轻松无忧找mac软件资源
  15. vue项目中别个访问你的本地调试需要改东西
  16. python中的keys、values、items
  17. (转)2018几大主流的UI/JS框架——前端框架 [Vue.js(目前市场上的主流)]
  18. 模块二 hashlib模块、configparser模块、logging模块
  19. c#while循环注意continue的地方
  20. DIV+CSS 按比例等分

热门文章

  1. Android:实现数组之间的复制
  2. lua的split函数
  3. Java多线程5:线程等待与唤醒
  4. C++:虚函数的引入
  5. @interface java注解
  6. 【笨嘴拙舌WINDOWS】编码历史
  7. iOS开发:本地数据存储-NSUserDefaults
  8. Jquery实现让滚动条始终保持在最下方
  9. 设置mysql的interactive_timeout和wait_timeout的值
  10. [转] jQuery Infinite Ajax Scroll(ias) 分页插件介绍