poj1066--Treasure Hunt(规范相交)
2024-09-02 00:39:49
题目链接:点击打开链接
题目大意:一个正方形的墓葬内有n堵墙,每堵墙的两个顶点都在正方形的边界上,如今这些墙将墓葬切割成了非常多小空间,已知正方形内的一个点上存在宝藏,如今我们要在正方形的外面去得到宝藏,对于每一个小空间,我们能够炸开它的随意一条边的中点,如今给出每堵墙的两个节点的坐标和宝藏的坐标,问假设要得到宝藏,须要炸的墙数最少是多少。
枚举正方形边界上的点作为进入正方形的节点,由这个点向宝藏连出一条线段,这条线段和多少个墙相交,那么就须要炸坏多少个墙,找出一个最小的值。
原因,由于每堵墙的两个节点都在边界上,所以假设和墙相交,那么就一定要跨过这道墙,所以须要炸掉它。
一定要是规范相交,由于假设枚举的点假设是一堵墙的节点,那么这堵墙是不应该被计算的。
(应该是枚举出边界上的小空间的中点,为了省事,直接枚举全部的点。
)
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std ;
#define eps 1e-8
#define zero(x) (((x) > 0 ? (x) : (-x)) < eps)
struct Point {
double x, y;
};
struct Line {
Point a, b;
}l[35], len[4];
int n ;
double xmult(Point p1, Point p2, Point p) {
return (p1.x-p.x)*(p2.y-p.y) - (p2.x-p.x)*(p1.y-p.y);
}
double dmult(Point p1, Point p2, Point p) {
return (p1.x-p.x)*(p2.x-p.x) + (p1.y-p.y)*(p2.y-p.y);
}
double distance(Point p1, Point p2) {
return sqrt((p1.x-p2.x)*(p1.x-p2.x)
+ (p1.y-p2.y)*(p1.y-p2.y));
}
int opposite_side(Point p1,Point p2,Line l) {
return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) < -eps;
}
int intersect_ex(Line u, Line v) {
return opposite_side(u.a, u.b, v)
&& opposite_side(v.a, v.b, u);
}
int solve(Line len) {
int i, num = 0;
for(i = 0; i < n; i++) {
if( intersect_ex(l[i],len) ) num++;
}
return num;
}
int main() {
int i , ans ;
while( scanf("%d", &n) != EOF ) {
ans = n ;
for(i = 0; i < n; i++) {
scanf("%lf %lf %lf %lf", &l[i].a.x, &l[i].a.y, &l[i].b.x, &l[i].b.y);
}
scanf("%lf %lf", &len[0].a.x, &len[0].a.y) ;
len[1] = len[2] = len[3] = len[0];
len[0].b.y = len[3].b.x = 100 ;
len[1].b.y = len[2].b.x = 0 ;
for(i = 0; i <= 100; i++) {
len[0].b.x = len[3].b.y = len[1].b.x = len[2].b.y = i ;
ans = min(ans, solve(len[0]));
ans = min(ans, solve(len[1]));
ans = min(ans, solve(len[2]));
ans = min(ans, solve(len[3]));
}
ans++ ;
printf("Number of doors = %d\n", ans) ;
}
return 0 ;
}
最新文章
- 知乎一道前端面试题详解,关于this的使用
- 【原】iOS学习之三种拨打电话方式的比较
- 转载:Chrome调试折腾记_(1)调试控制中心快捷键详解!!!
- (Java和C++)二进制date数据写进android保存为yuv格式
- 用distinct在MySQL中查询多条不重复记录值[转]
- 第一个app.总结
- python类的定义和使用
- [原创]Android中LocationManager的简单使用,获取当前位置
- JSP视频
- ACdream原创群赛(18)のAK&#39;s dream题解
- 如何让格斗游戏的横版过关(2) Cocos2d-x 2.0.4
- 11、手把手教你Extjs5(十一)模块界面的总体设计
- MVC页面静态化
- 开源:ASP.NET Aries 开发框架(已支持.NET Core)
- 关于C#中的++运算符的一些拓展思考
- koa文件上传中间件——koa-multer
- 20165221 JAVA第四周学习心得
- [leetcode]57. Insert Interval插入区间
- QT pro文件详细写法+实例
- Django基础十之Form和ModelForm组件