51nod--1265 四点共面 （计算几何基础， 点积， 叉积）
题目：1265 四点共面 基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题 收藏 关注 给出三维空间上的四个点（点与点的位置均不相同），判断这4个点是否在同一个平面内（4点共线也算共面）。如果共面，输出”Yes”，否则输出”No”。 Input 第1行：一个数T，表示输...
【XSY2760】nonintersect 计算几何
题目描述平面上有\(n\)条线段，你要擦掉所有线段但保留原有的\(2n\)个端点，然后连接这些端点形成\(n\)条不相交的线段，每个端点只能在一条线段中。假设你画的线段总长为\(Y\)，原有线段的总长为\(X\)，你要满足\(Y\geq \frac{2}{\pi}X\)\(n\leq 5000\)题...
ZOJ3238 Water Ring(计算几何)
题意：给你一个圆形和很多个矩形，然后要你求圆形的圆周有多少被矩形覆盖。思路：比赛的时候是有思路的了，不过一直在调别的题，最后剩下30分钟肯定来不及敲。想法是这样的，要是我们可以求出每个矩形覆盖了圆周的哪些区间，我们最后就对这些区间排序然后求区间和就好了，但是问题是怎么知道哪些区间是要的，哪些区间是不...
POJ 1654 Area 计算几何
#include<stdio.h>#include<string.h>#include<iostream>#include<math.h>using namespace std;int dx[]={,,,,,,,-,-,-};int dy[]={,-,...
POJ 1410 Intersection（计算几何）
题目大意：题目意思很简单，就是说有一个矩阵是实心的，给出一条线段，问线段和矩阵是否相交解题思路：用到了线段与线段是否交叉，然后再判断线段是否在矩阵里面，这里要注意的是，他给出的矩阵的坐标明显不是左上和右下的坐标，需要自己去判断下左上点与右下点的坐标。#include <map>#incl...
计算几何---凸包问题（Graham/Andrew Scan ）
概念凸包(Convex Hull)是一个计算几何（图形学）中的概念。用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有点的。严谨的定义和相关概念参见维基百科：凸包。也被称为：Graham/Andrew Scan 算法。在二维欧几里得空间中，凸包可想...
Codeforces 32E Hide-and-Seek 乞讨2关于镜面反射点 计算几何
主题链接：点击打开链接必须指出的是，反射镜和2个人共线是不是障碍，但根据该壁其他情况#include<cstdio>#include<iostream>#include<algorithm>#include<string.h>#include<m...
poj 2653 计算几何
#include <iostream> #include <cstring> #include <algorithm> #include <cmath> #include <cstdio> using namespace std; str...
【BZOJ-1502】月下柠檬树 计算几何 + 自适应Simpson积分
1502: [NOI2005]月下柠檬树Time Limit: 5 Sec Memory Limit: 64 MBSubmit:1017 Solved: 562[Submit][Status][Discuss]DescriptionInput文件的第1行包含一个整数n和一个实数alpha，表示柠...
洛谷P1742 最小圆覆盖（计算几何）
题面传送门题解之前只是在抄题解……这篇才算是真正自己想的吧……首先我们把输入序列给\(random\)一下防止出题人好心送你一个毒瘤序列我们设\(r\)为当前最大半径，\(o\)为此时对应圆心先说一下算法过程：令前\(i-1\)个点的最小覆盖圆为\((o,r)\)如果第\(i\)个点在这个圆中，直接...
洛谷CF1071E Rain Protection（计算几何，闵可夫斯基和，凸包，二分答案）
洛谷题目传送门CF题目传送门对于这题，我无力吐槽。虽然式子还是不难想，做法也随便口胡，但是一些鬼畜边界情况就是判不对。首先显然二分答案。对于每一个雨滴，它出现的时刻我们的绳子必须落在它上面。把绳子的上下端点用二元组\((a,b)\)表示，因为三个点\((a,0)(x_i,y_i)(b,h)\)共线，...
HDU 4998 Rotate (计算几何)
HDU 4998 Rotate (计算几何)题目链接http://acm.hdu.edu.cn/showproblem.php?pid=4998DescriptionNoting is more interesting than rotation!Your little sister likes t...
BZOJ3775: 点和直线（计算几何+拉格朗日乘数法）
题面传送门题解劲啊……没有和\(Claris\)一样推，用了类似于\(Shinbokuow\)推已知点求最短直线的方法，结果\(WA\)了好几个小时，拿\(Claris\)代码拍了几个小时都没找到\(bug\)在哪儿，最后发现是我一个除法的地方忘记除数为\(0\)的情况了……甘霖娘……公式恐惧症患者...
2018牛客网暑假ACM多校训练赛（第三场）I Expected Size of Random Convex Hull 计算几何,凸包,其他
原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round3-I.html题目传送门 - 2018牛客多校赛第三场 I题意在一个给定的三角形内部随机选择 $n$ 个点，问这些点构成的凸包的期望顶点数。$3\leq n\l...
[转] 计算几何模板Orz
#include<math.h> #define MAXN 1000 #define offset 10000 #define eps 1e-8 #define PI acos(-1.0)//3.14159265358979323846 //判断一个...
计算几何总结（Part 1~2）
Preface对于一个初三连三角函数都不会的蒟蒻来说计算几何简直就是噩梦。反正都是要学的也TM没办法，那就慢慢一点点学起吧。计算几何要有正确的板子，不然那种几百行CODE的题写死你。本蒟蒻的学习过程参考dalao's blog和lrj的蓝书Part 1——基本结构命名与精度控制首先计算几何就是在一个...
FZU 2099 魔法阵（计算几何）
Problem 2099 魔法阵Accept: 120 Submit: 289Time Limit: 1000 mSec Memory Limit : 32768 KB Problem Description两个正三角形和一个圆组成一个魔法阵，如图，圆心和正三角形内心重合，三角形的重叠...
POJ 2318 TOYS（计算几何）
题目大意：有一个矩形盒子，盒子里会有一些木块线段，并且这些线段是按照顺序给出的，有n条线段，把盒子分层了n+1个区域,然后有m个玩具，这m个玩具的坐标是已知的，问最后每个区域有多少个玩具解题思路：因为线段是有序给出，所以不用排序，判断某个点在哪个区域，采用二分法，将某个点和线段的叉积来判断这个点是在...
POJ 2031 Building a Space Station【最小生成树+简单计算几何】
You are a member of the space station engineering team, and are assigned a task in the construction process of the station. You are expected to write ...
POJ_1269_Intersecting_Lines_(计算几何基础)
描述http://poj.org/problem?id=1269给出两条直线,判断它们是平行,重合,还是相交,如果相交,求出交点.分析比较裸的一道题.学习了直线的写法(参数方程) #include <cstdio> #include <cmath> using namespa...