线段相交 poj 1066
2024-08-23 06:37:12
// 线段相交 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 ;
}
最新文章
- HackerNews——《Pokemon Go玩家存在巨大的安全风险》
- 堆排序分析及php实现
- ASP.NET的一般处理程序对图片文件的基本操作
- php防止刷新(流量攻击)的一段代码
- C++编译器默默编写并调用哪些函数
- 被误解的 MVC 和被神化的 MVVM
- 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
- 寻找数列中第k大的数算法分析
- cocos2d-x 截取屏幕可见区域
- USACO Section 1.3 Mixing Milk 解题报告
- 【开发技术】对文件内容进行加密-java
- mysql 2pc理解
- 我的数据,我做主——RecoveryManager Plus
- 上这个资源网站,让你轻松无忧找mac软件资源
- vue项目中别个访问你的本地调试需要改东西
- python中的keys、values、items
- (转)2018几大主流的UI/JS框架——前端框架 [Vue.js(目前市场上的主流)]
- 模块二 hashlib模块、configparser模块、logging模块
- c#while循环注意continue的地方
- DIV+CSS 按比例等分