暑假集训 day07
source link: https://wuhu-z.github.io/2021/08/29/21%E6%9A%91%E5%81%87%E9%9B%86%E8%AE%ADday07/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
向量线段相关
1.点积（点乘）
a.x∗b.x+a.y∗b.y
2.差积（叉乘）
a.x∗b.y−a.y∗b.x
3.转角公式
逆时针旋转角度B
原：(cosAr,sinAr)
现：(cos(A+B)r,sin(A+B)r)=((cosAcosB−sinAsinB)r,(sinAcosB+cosAsinB)r)
即：**(x,y)−>(xcosB−ysinB,xsinB+ycosB)**
4.极角排序
极角：在极坐标系中，平面上任何一点到极点的连线和极轴的夹角叫做极角
- atan2:这是一个给定三角形对边和邻边算角的函数，在cmath库中对每个向量求angle=atan2(a.y,a.x)后直接排序即可
举例：atan2(1,1)=0.78,atan2(1,0)=1.57
- 叉积: 叉积的正负可以判断左右关系，所以在最大跨角不超过180度的时候可以 非常好地实现，否则有可能随机一个起点绕好几圈
5.两直线夹角
theta =atan2(x*y,x&y)
叉积是平行四边形，底乘高；点积是底乘投影。
更特殊点，该夹角是有向夹角，从x向量旋转到y，逆时针是正角、顺时针是负角
6.两直线交点
面积比->线段比->定比分点
Node Crosss(Node a1,Node a2,Node b1,Node b2)
{
Node a=a2-a1,b=b2-b1,c=b1-a1;
if(fabs(b*a)<1e-12) return (Node){-1e9,-1e9};//平行
double t=(b*c)/(b*a);
return a1+(a^t);
}
7.判断两线段是否相交：
a1,a2,b1,b2为两条直线的两个端点
如果满足(b1−a1)×(b1−a2)和(b2−a1)×(b2−a2)不同号，并且(a1−b1)×(a1−b2)和(a2−b1)×(a2−b2)不同号，则两线段相交，叫跨立实验。
多边形相关
1.凸包
找到最下的点设为原点，将剩下的点用叉积极角排序
用单调栈维护凸包，当(A[i]−A[sta[top−1]])×(A[sta[top]]−A[sta[top−1]])为非负时需要弹栈
int cmp1(const Node&A,const Node&B) {return A.y<B.y||(A.y==B.y&&A.x<B.x);}
int cmp2(const Node&A,const Node&B) {return A*B>0||(A*B==0&&A.dis()<B.dis());}
//这个表示如果两向量共线，把短的放前面（方便被踢开）
void Tubao()
{
sort(A+1,A+n+1,cmp1);//找到最底下的点
for(int i=n;i>=1;i--) A[i]=A[i]-A[1];
sort(A+2,A+n+1,cmp2);//极角排序
for(int i=1;i<=n;sta[++top]=i,i++)
while(top>=2&&(A[i]-A[sta[top-1]])*(A[sta[top]]-A[sta[top-1]])>=0) top--;
n=top;for(int i=1;i<=top;i++) A[i]=A[sta[i]];
}
2.判断点是否在多边形内
从该点向右引射线，与多边形交奇数次即在其内。
顺时针+1，逆时针-1，注意与顶点重合的情况
Practice：Codeforces375C Circling Round Treasures
3.判断点是否在凸包内：
先判定和边界的关系
然后找到与其极角相邻的两点，凭此判断
须保证A[1]=(0,0)
ll in(Node a)
{
if(a*A[1]>0||A[tot]*a>0) return 0;
ll ps=lower_bound(A+1,A+tot+1,a,cmp2)-A-1;
return (a-A[ps])*(A[ps%tot+1]-A[ps])<=0;
}
4.求多边形面积
逆时针极角排序后直接用叉积求
double CalcS()
{
double res=0;
for(int i=2;i<node;i++) res+=(A[i]-A[1])*(A[i+1]-A[1]);
return res/2;
}
5.三角形重心
hdu 1392
题目：
思路：
建立凸包即可，只不过有个坑点，明明是包围住，结果n==2的时候，只用连住就行了，
代码：
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn=109;
struct node
{
double x,y;
} edge[maxn],ans[maxn];
bool cmp(node a,node b)
{
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
double mul(node a,node b,node c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
double dis(node a,node b)
{
return sqrt((a.x*1.0-b.x)*(a.x*1.0-b.x)+(a.y*1.0-b.y)*(a.y*1.0-b.y));
}
int solve(int n)
{
int len=0;
for(int i=0; i<n; i++)
{
while(len>1&&mul(ans[len-2],ans[len-1],edge[i])<=0) len--;
ans[len++]=edge[i];
}
int k=len;
for(int i=n-1; i>=0; i--)
{
while(len>k&&mul(ans[len-2],ans[len-1],edge[i])<=0) len--;
ans[len++]=edge[i];
}
return len-1;
}
int main()
{
int t,n;
while(~scanf("%d",&n),n)
{
for(int i=0; i<n; i++)
scanf("%lf%lf",&edge[i].x,&edge[i].y);
sort(edge,edge+n,cmp);//排序
int len=solve(n);
double ans1=0;
for(int i=0; i<len; i++)
ans1+=dis(ans[i],ans[i+1]);
if(len==2)//n==2要特判
ans1/=2.0;
printf("%.2lf\n",ans1);
}
return 0;
}
hdu2202
题目：
思路：
利用三角形外接圆，即找到一个最小的圆能够包围所有的点（利用凸包），那么在这个圆上至少存在三个点以上，所以，此时就可以使用暴力求出最大三角形面积了；
代码：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iomanip>
using namespace std;
const int Max=50005;
struct Node
{
int x;
int y;
}a[Max],b[Max];
int cmp(Node m,Node n)
{
if(m.x==n.x)
return m.y<n.y;
else
return m.x<n.x;
}
int Count(Node i,Node j,Node k) //就算三角形的面积；
{
int x1=i.x-j.x;
int y1=i.y-j.y;
int x2=k.x-j.x;
int y2=k.y-j.y;
return(x1*y2-x2*y1);
}
int convex(int n) //凸包计算；求出在圆上的点得数量m；和坐标。
{
sort(a,a+n,cmp);
int m=0,i,j,k;
for(i=0;i<n;i++)
{
while(m>1&&Count(b[m-1],a[i],b[m-2])<=0)
m--;
b[m++]=a[i];
}
k=m;
for(i=n-2;i>=0;i--)
{
while(m>k&&Count(b[m-1],a[i],b[m-2])<=0)
m--;
b[m++]=a[i];
}
if(n>1)
m--;
return m;
}
int main()
{
int i,j,k,n,m;
int sum=0;
while(cin>>n)
{
for(i=0;i<n;i++)
cin>>a[i].x>>a[i].y;
sum=0;
m=convex(n);
//cout<<m<<endl;
for(i=0;i<m;i++)
for(j=i+1;j<m;j++)
for(k=j+1;k<m;k++)
{
sum=max(sum,Count(b[i],b[j],b[k]));
}
//sum=sum/2.0;
printf("%.2lf\n",0.5*sum);
// cout<<fixed<<setprecision(2)<<sum<<endl;
}
return 0;
}
hdu3803
题目：
思路：
根据面积的比例计算交点
代码：
#include <iostream>
using namespace std;
#define LL long long
// 符号函数
int sign(const LL &v){
if (v > 0) return 1;
else if (v == 0) return 0;
else return -1;
}
struct Fract{
LL z, m;
LL gcd(LL a, LL b){
while (b){
LL r = a % b;
a = b;
b = r;
}
return a;
}
void Create(LL a, LL b = 1) {
LL t = gcd(a, b);
a /= t, b /= t;
z = a, m = b;
if (m < 0) m = -m, z = -z;
}
void print() {
if (m == 1) printf("%lld", z);
else printf("%lld/%lld", z, m);
}
};
struct Point{
LL x, y;
// 与点p是否是为同一个点
bool operator==(const Point &p){
return x == p.x && y == p.y;
}
// 当前点p(x,y)与点p1和p2构成的向量p->p1、p->p2的叉积
LL cross(const Point &p1, const Point &p2){
return (p1.x - x)*(p2.y - y) - (p1.y - y)*(p2.x - x);
}
};
struct Segment{
// 起点
Point s;
// 终点
Point t;
// 线段的两个端点重合，则退化成一个点
bool isPoint(){
return s == t;
}
// 点p是否在线段上
bool has(Point &p){
if(cross(p) != 0) return false;
if(s.x == t.x)
return p.y <= max(s.y, t.y) && p.y >= min(s.y, t.y);
else
return p.x <= max(s.x, t.x) && p.x >= min(s.x, t.x);
}
// 当前线段与线段seg是否重合
bool operator==(const Segment &seg){
return (s == seg.s && t == seg.t) || (s == seg.t && t == seg.s);
}
// 点p(x,y)与线段的端点构成的向量p->s、p->t的叉积
LL cross(Point &p){
return p.cross(s, t);
}
// 与线段seg相交
// 返回值1：有一个交点，交点存储在x、y中
// 返回值0：无交点
// 返回值-1：无穷多个交点
int interSection(Segment &seg, Fract &x, Fract &y){
int res;
if(isPoint() && seg.isPoint()){// 线段都是点
if(*this == seg) res = 1, x.Create(s.x), y.Create(s.y);// 重合
else res = 0;// 不重合
}
else if(isPoint() || seg.isPoint()){// 有一线段是点
if(isPoint() && seg.has(s))
res = 1, x.Create(s.x), y.Create(s.y);
else if(seg.isPoint() && has(seg.s))
res = 1, x.Create(seg.s.x), y.Create(seg.s.y);
else
res = 0;
}
else{// 线段都不是点
LL a, b, c, d;
int s1, s2, s3, s4;
s1 = sign(a = seg.cross(s));
s2 = sign(b = seg.cross(t));
s3 = sign(c = this->cross(seg.s));
s4 = sign(d = this->cross(seg.t));
if((s1^s2) == -2 && (s3^s4) == -2){ // 1^-1 = -2
res = 1;
x.Create(b*s.x - a*t.x, b - a);
y.Create(b*s.y - a*t.y, b - a);
}
else if(a == 0 && b == 0){
if(seg.has(s) && seg.has(t))// 是seg子线段
res = -1;
else if(seg.has(s)){ // s在线段seg上, t不在线段seg上
if((s == seg.s && !has(seg.t))||(s == seg.t && !has(seg.s)))
res = 1, x.Create(s.x), y.Create(s.y);
else
res = -1;
}
else if(seg.has(t)){// t在线段seg上, s不在线段seg上
if((t == seg.s && !has(seg.t))||(t == seg.t && !has(seg.s)))
res = 1, x.Create(t.x), y.Create(t.y);
else
res = -1;
}
else{
if(has(seg.s)) res = -1; // seg是子线段
else res = 0; // 无重叠
}
}
else if(a == 0){ // b != 0
if(seg.has(s)) res = 1, x.Create(s.x), y.Create(s.y);
else res = 0;
}
else if(b == 0){ // a != 0
if(seg.has(t)) res = 1, x.Create(t.x), y.Create(t.y);
else res = 0;
}
else if(c == 0){ // d != 0
if(has(seg.s)) res = 1, x.Create(seg.s.x), y.Create(seg.s.y);
else res = 0;
}
else if(d == 0){ // c != 0
if(has(seg.t)) res = 1, x.Create(seg.t.x), y.Create(seg.t.y);
else res = 0;
}
else{ // a != 0 && b != 0
res = 0;
}
}
return res;
}
};
int main()
{
int T;
Segment ab, cd;
Fract x, y;
int res ;
scanf("%d", &T);
while(T--){
scanf("%lld %lld %lld %lld", &ab.s.x, &ab.s.y, &ab.t.x, &ab.t.y);
scanf("%lld %lld %lld %lld", &cd.s.x, &cd.s.y, &cd.t.x, &cd.t.y);
res = ab.interSection(cd, x, y);
if(res == 1) {
printf("1\n");
x.print(), printf(" "), y.print();
printf("\n");
}
else if (res == 0) printf("0\n");
else printf("INF\n");
}
return 0;
}
hdu2036
题目：
思路:
逆时针极角排序后直接用叉积求
代码：
import java.util.Scanner;
public class Main {
public static double area(double x1,double y1,double x2,double y2){
double a=(x1*y2-y1*x2)/2;//向量的叉乘等于两个向量所围成的三角形面积
return a;//向量a叉乘向量b=0.5*|a|*|b|*sin(C)=s(面积)
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true)
{
int t = sc.nextInt();
if(t==0)break;
double []a = new double[2*t];
double s=0;
for(int i=0;i<2*t;i++)
{
a[i]=sc.nextDouble();
}
for(int i=0;i<t*2;i+=2){
if(i==t*2-2){
s+=area(a[i],a[i+1],a[0],a[1]);
}else{
s+=area(a[i],a[i+1],a[i+2],a[i+3]);
}
}
System.out.printf("%.1f",s);
System.out.println();
}
sc.close();
}
}
hdu2108
题目：
思路：
遍历各边叉乘，若小于0则失败（注意各边同向）
代码：
import java.util.Scanner;
class node
{
public int x=0;
public int y=0;
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true)
{
node a []= new node[10005];
int t = sc.nextInt();
if(t==0)break;
for(int i=0;i<t;i++)
{
a[i]=new node();
a[i].x= sc.nextInt();
a[i].y= sc.nextInt();
}
a[t]=new node();
a[t+1]= new node();
a[t]=a[0];
a[t+1]=a[1];
boolean flag=true;
for(int i=0;i<t;i++)
{
double sum = (a[i+1].x-a[i].x)*(a[i+2].y-a[i+1].y)-(a[i+2].x-a[i+1].x)*(a[i+1].y-a[i].y);
if(sum<0)
{
flag=false;
break;
}
}
if(flag) System.out.println("convex");
else System.out.println("concave");
}
sc.close();
}
}
Recommend
-
42
Day1 开场看题，T1计算几何扔掉，T2&T3应该是挺正常的题可以搞搞。 写完T1的10分后开始想T2，但是怎么想都觉得Πpi^ai没法判断是否>=1，取ln也不靠谱，感觉可能有高论了。。 于是又去看T3，把题意转化了一下...
-
22
Kubernetes 是谷歌开源的容器集群编排平台，是一个完备的分布式系统支撑平台，为容器化应用提供部署运行、资源调度、服务发现和动态伸缩等一系...
-
12
做 Android 的人都知道 ButterKnife，很多人也因为 ButterKnife 而知道了 Dagger。然而同为注解 + 自动赋值的库，Dagger 却远不像 ButterKnife 那样受欢迎。 为什么？比较容易归结的原因是：Dagger 太难了，超级难；...
-
7
2天集训 | 教你如何完整地体验一款产品，撰写产品体验报告！ | 运营派 ¥0 ¥99
-
8
赵睿落选中国男篮集训名单实时讨论:34.7W 5月14日，中国男篮公布了东京奥运会落选赛和2021年亚洲杯预选赛集训名单，易建联郭艾伦周琦领衔，赵睿落选！看看吧友们如何分析。
-
3
kmp算法图解KMP首先说明前缀字符串不能包含最后一个字符，后缀字符串亦然 现在我们先看一个图：第一个长条代表主串，第二个长条代表子串。红色部分代表两串中已匹配的部分， 再具...
-
5
第一次暑期测试题目： 思路：...
-
5
Spring管理Bean-IOC-05 3.基于注解配置bean 3.3自动装配 基本说明： 基于注解配置bean，也可以实现自动装配，使用的注解是：@Aut...
-
4
MyBatis的关联映射 Mybatis的关联映射 实际的开发中，对数据库的操作常常会涉及到多张表，这在面向对象中就...
-
4
功能03-优惠券秒杀03 4.功能03-优惠券秒杀 4.6Redisson的分布式锁
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK