计算几何中的凸包类问题
P2116 城墙
求距离凸多边形为 L L L的最小外围周长。
a n s = ans= ans=凸包周长+ 2 π L 2\pi L 2πL
图参考题解区。
至于圆弧周长等于 2 π L 2\pi L 2πL ，是因为内角和为 360 360 360，这个容易证得，题解区也有。
P4166 [SCOI2007]最大土地面积
求四个点组成得最大多边形面积。
结论：若凸包点数大于3，则这四个点一定都在凸包上。
若凸包点数小于3，则答案为0。
若凸包点数等于3，则该四边形是一个凹四边形，凸包上的3个点会和不在凸包上的点组成一个凹四边形，枚举不在凸包上点计算即可。
凸包点数大于3时，考虑枚举对角线 i , j i,j i,j ，然后类似旋转卡壳扫 i , x , j i,x,j i,x,j 这个三角形的最大面积， i , j , y i,j,y i,j,y 这个三角形的最大面积。
然后求和取最大值即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=2e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0)
void Print(int *a,int n){
for(int i=1;i<n;i++)
printf("%d ",a[i]);
printf("%d\n",a[n]);
}
struct P{
double x,y;
int id;
}a[N],s[N];
int top,n;
double cross(P a,P b,P c){
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
double dis(P a,P b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool cmp(P u,P v){
double t=cross(u,v,a[1]);
return t>0||(t==0&&dis(u,a[1])<dis(v,a[1]));
}
void graham(){
s[top=1]=a[1];
for(int i=2;i<=n;){
if(top>1&&cross(s[top-1],a[i],s[top])>=0) top--;
else s[++top]=a[i++];
}
}
double rt_cp(){
//s[top+1]=s[1];
double ans=0;
if(top<3) return 0;
else if(top==3){
ll mn=1e18;
ans=abs(cross(s[1],s[2],s[3]));
for(int i=1;i<=n;i++){
if (s[1].id==a[i].id||s[2].id==a[i].id||s[3].id==a[i].id) continue;
ll s1=abs(cross(a[i],s[1],s[2]));
ll s2=abs(cross(a[i],s[2],s[3]));
ll s3=abs(cross(a[i],s[3],s[1]));
mn=min({mn,s1,s2,s3});
}
if(mn!=1e18) ans-=mn;
else ans=0;
}
else {
for(int i=1;i<=top;i++){
int x=i%top+1,y=(i+2)%top+1;
for(int j=i+2;j<=top;j++){
while(x%top+1!=j&&fabs(cross(s[i],s[x+1],s[j]))>fabs(cross(s[i],s[x],s[j])))
x=x%top+1;
while(y%top+1!=i&&fabs(cross(s[i],s[j],s[y+1]))>fabs(cross(s[i],s[j],s[y])))
y=y%top+1;
ans=max(ans,fabs(cross(s[i],s[x],s[j]))+fabs(cross(s[i],s[j],s[y])));
}
}
}
return ans/2.0;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y),a[i].id=i;
int id=1;
for(int i=2;i<=n;i++)
if(a[i].x<a[id].x||(a[i].x==a[id].x&&a[i].y<a[id].y)) id=i;
swap(a[1],a[id]);sort(a+2,a+n+1,cmp);graham();
printf("%.3f\n",rt_cp());
}
2019ICPC TaiBei L- Largest Quadrilateral
双倍经验，不过此题卡 d o u b l e double double ，全部换成long long，因为答案要么.0，要么时.5 所以特判下即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=5e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0)
void Print(int *a,int n){
for(int i=1;i<n;i++)
printf("%d ",a[i]);
printf("%d\n",a[n]);
}
struct P{
ll x,y;
int id;
}a[N],s[N];
int top,n;
ll cross(P a,P b,P c){
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
ll dis(P a,P b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool cmp(P u,P v){
ll t=cross(u,v,a[1]);
return t>0||(t==0&&dis(u,a[1])<dis(v,a[1]));
}
void graham(){
s[top=1]=a[1];
for(int i=2;i<=n;){
if(top>1&&cross(s[top-1],a[i],s[top])>=0) top--;
else s[++top]=a[i++];
}
}
void rt_cp(){
//s[top+1]=s[1];
ll ans=0;
if(top<3) {
printf("0\n");return;
}
else if(top==3){
ll mn=1e18;
ans=abs(cross(s[1],s[2],s[3]));
for(int i=1;i<=n;i++){
if (s[1].id==a[i].id||s[2].id==a[i].id||s[3].id==a[i].id) continue;
ll s1=abs(cross(a[i],s[1],s[2]));
ll s2=abs(cross(a[i],s[2],s[3]));
ll s3=abs(cross(a[i],s[3],s[1]));
mn=min({mn,s1,s2,s3});
}
if(mn!=1e18) ans-=mn;
else ans=0;
}
else { s[++top]=s[1];
for(int i=1;i<=top;i++){
int x=i%top+1,y=(i+2)%top+1;
for(int j=i+2;j<=top;j++){
while(x%top+1!=j&&abs(cross(s[i],s[x+1],s[j]))>abs(cross(s[i],s[x],s[j])))
x=x%top+1;
while(y%top+1!=i&&abs(cross(s[i],s[j],s[y+1]))>abs(cross(s[i],s[j],s[y])))
y=y%top+1;
ans=max(ans,abs(cross(s[i],s[x],s[j]))+abs(cross(s[i],s[j],s[y])));
}
}
}
if(ans&1){
printf("%lld.5\n",ans/2);
}
else printf("%lld\n",ans/2);
}
int main(){
int t;scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].x,&a[i].y),a[i].id=i;
int id=1;
for(int i=2;i<=n;i++)
if(a[i].x<a[id].x||(a[i].x==a[id].x&&a[i].y<a[id].y)) id=i;
swap(a[1],a[id]);sort(a+2,a+n+1,cmp);graham();
rt_cp();
}
}
P3187 [HNOI2007]最小矩形覆盖
结论：最小矩形的一条边必定与凸包上某条边重合，因此考虑枚举该边，维护三个点，顶点，最左边的点，最右边的点，取最值即可。
时间复杂度： O ( n l g o n + n ) O(nlgon+n) O(nlgon+n)
代码还没写，来自题解区。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define maxn 50021
#define F(a) (a<0 ? a=-a : 0)
using namespace std;
int top,n;
struct P{
double x,y;
P(double a=0,double b=0):x(a),y(b){}
bool operator<(const P& b)const{return x==b.x?y<b.y:x<b.x;}
}p[maxn],s[maxn],q[10];
typedef P vec;
vec operator+(vec a,vec b){return vec(a.x+b.x,a.y+b.y);}
vec operator-(P a,P b){return vec(a.x-b.x,a.y-b.y);}
vec operator*(vec a,double p){return vec(a.x*p,a.y*p);}
vec operator/(vec a,double p){return vec(a.x/p,a.y/p);}
double cross(vec a,vec b){return a.x*b.y-a.y*b.x;}
double area(P a,P b,P c){return fabs(cross(a-b,a-c));}
double dot(vec a,vec b){return a.x*b.x+a.y*b.y;}
double len(vec a){return sqrt(a.x*a.x+a.y*a.y);}
double angle(vec a,vec b){return acos(dot(a,b)/len(a)/len(b));}
bool cmp(P a,P b){return a.y==b.y ? a.x > b.x : a.y < b.y;}
void make(){
sort(p+1,p+1+n);
for(int i=1;i<=n;i++){
while(top>1&&cross(s[top]-s[top-1],p[i]-s[top])<=0)top--;
s[++top]=p[i];
}int m=top;
for(int i=n-1;i>=1;i--){
while(top>m&&cross(s[top]-s[top-1],p[i]-s[top])<=0)top--;
s[++top]=p[i];
}
}
void solve(){
double tmp,ans=1e100;
int a,b,c;s[top+1]=s[1];
a=b=c=2;
for(int i=2;i<=top;i++){
while(cross(s[a+1]-s[i],s[i-1]-s[i])>=cross(s[a]-s[i],s[i-1]-s[i]))a=a%top+1;
while(dot(s[b+1]-s[i],s[i-1]-s[i])<=dot(s[b]-s[i],s[i-1]-s[i]))b=b%top+1;
if(i==2)c=a;
while(dot(s[c+1]-s[i-1],s[i]-s[i-1])<=dot(s[c]-s[i-1],s[i]-s[i-1]))c=c%top+1;
double dis=len(s[i]-s[i-1]);
double L=dot(s[c]-s[i],s[i-1]-s[i])/dis;F(L);
double R=dot(s[b]-s[i-1],s[i]-s[i-1])/dis;F(R);
double H=area(s[i],s[i-1],s[a])/len(s[i]-s[i-1]);F(H);
tmp=(L+R-dis)*H;
if(tmp<ans){
ans=tmp;
q[1]=s[i]-(s[i]-s[i-1])*(L/dis);
q[2]=q[1]+(s[i]-s[i-1])*((R+L-dis)/dis);
q[3]=q[2]+(s[b]-q[2])*(H/len(s[b]-q[2]));
q[4]=q[3]+(s[i-1]-s[i])*((R+L-dis)/dis);
}
}
printf("%.5lf\n",ans);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
make();solve();
int st=0;q[0].y=1e9;
for(int i=1;i<=4;i++)if(q[i].y<q[st].y||(q[i].y==q[st].y&&q[i].x<q[st].x))st=i;
if(fabs(q[st].x)<=1e-8)q[st].x=0;
if(fabs(q[st].y)<=1e-8)q[st].y=0;
printf("%.5lf %.5lf\n",q[st].x,q[st].y);
for(int i=0;i<3;i++){
if(fabs(q[(i+st)%4+1].x)<=1e-8)q[(i+st)%4+1].x=0;
if(fabs(q[(i+st)%4+1].y)<=1e-8)q[(i+st)%4+1].y=0;
printf("%.5lf %.5lf\n",q[(i+st)%4+1].x,q[(i+st)%4+1].y);
}
return 0;
}
P3744 李彬的几何
移动最小距离使凸多边形变为非凸多边形。
显然是移动相邻三个点 A , B , C A,B,C A,B,C，移动的距离就是 B B B到直线 A C AC AC的距离除以 2 2 2。因为三个点都能移动，即 A , C A,C A,C 和 B B B 相互移动 d 2 \dfrac{d}{2} 2d即可。
求点到直线距离，可以用叉积。
B D = A C × A B ∣ A C ∣ BD=\dfrac{AC\times AB}{|AC|} BD=∣AC∣AC×AB
时间复杂度： O ( n ) O(n) O(n) 代码参考题解区。
#include <cstdio>
#include <cmath>
#include <algorithm>
#define INF 1000000000.0
using namespace std;
struct Point {
double x, y; //横纵坐标
Point (double x = 0, double y = 0) : x(x), y(y) {}
};
Point point[1010];
Point operator - (Point x, Point y) {
return Point(x.x-y.x, x.y-y.y);
}
double Cross (Point x, Point y) {
return fabs(x.x*y.y - x.y*y.x);
}
double Len (Point x, Point y) {
return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double solve (int i) { //计算点到直线距离，i即A，i+1即B，i+2即C
Point x1 = point[i]-point[i+2];
Point x2 = point[i]-point[i+1];
return Cross(x1, x2)/Len(x1, Point(0, 0));
}
int main () {
int n;
double ans = INF;
scanf ("%d", &n);
for (int i = 0; i < n; i++) {
scanf ("%lf %lf", &point[i].x, &point[i].y);
}
point[n] = point[0]; //由于要枚举下标n-1，所以把n和n+1也填上，避免取模
point[n+1] = point[1];
for (int i = 0; i < n; i++) { //枚举点A
ans = min(ans, solve (i));
//printf ("%.10lf\n", ans/2); 用于调试的代码
}
printf ("%.10lf\n", ans/2);
return 0;
}
P4894 GodFly求解法向量
两个相交向量的法向量，等于两向量的叉积。
关于三阶行列式的计算可以参考代数余子式
P2785 物理1（phsic1）- 磁通量
就是求多边形的面积，直接上叉积即可，注意最后取绝对值。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
#define mst(a,b) memset(a,b,sizeof a)
struct P{
double x,y;
}a[N];
int main(){
int n;double B;
scanf("%d%lf",&n,&B);
for(int i=0;i<n;i++){
scanf("%lf%lf",&a[i].x,&a[i].y);
}
a[n].x=a[0].x,a[n].y=a[0].y;
double s=0;
for(int i=0;i<n;i++) s+=(a[i].x*a[i+1].y-a[i+1].x*a[i].y);
s/=2;
//如果点是顺时针读入就 加上绝对值 s=fabs(s);
printf("%.4f\n",fabs(s)*B);
return 0;
}
P3194 [HNOI2008]水平可见直线
就是维护一个下凸包。
此时可以弹出 A B AB AB，注意斜率相同的时候取 b b b较大的。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,ans[N],s[N],top;
struct node{
int a,b,id;
}a[N];
bool cmp(node x,node y){
if(x.a!=y.a) return x.a>y.a;//先按斜率再按截距排序
else return x.b>y.b;
}
double calc(int i,int j){//计算交点
return ((1.0*(a[i].b-a[j].b))/(a[j].a-a[i].a));
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d %d",&a[i].a,&a[i].b);a[i].id=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
if(a[i].a==a[i-1].a&&i>1) continue; //去重
while(top>1&&calc(s[top],i)>=calc(s[top],s[top-1])) top--;//若当前交点在上一个交点左边,则上一条直线被覆盖,弹出栈
s[++top]=i;
ans[top]=a[i].id;
}
sort(ans+1,ans+top+1);
for(int i=1;i<=top;i++) printf("%d ",ans[i]);
return 0;
}
也可以求在半平面交上的线段即可。
注意排序时，如果斜率相同， b b b大的放前面，然后去重的时候特判一下
if(i>1&&A[i].g==A[i-1].g) continue;
这样就只保留了前面的。
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-12;
const int N=1e5+5;
#define il inline
struct P{
double x,y;
}p[N];
struct L{
P p1,p2; double g;
int id;
}A[N],q[N];
double ANS;
int n,top,bot,tot;
bitset<N>vis;
il P operator-(P a,P b){
P t; t.x=a.x-b.x; t.y=a.y-b.y;
return t;
}
il double operator*(P a,P b){ //叉乘.
return a.x*b.y-b.x*a.y;
}
il bool operator<(L a,L b){
if(a.g==b.g) return (b.p2-a.p1)*(b.p1-a.p1)<0;//越靠右，排名越靠前，会被覆盖掉
return a.g<b.g;
}
il P inter(L a,L b){
double k1,k2;//k1 k2 是两条线段四点连线所形成的两个三角形面积
k1=(b.p1-a.p1)*(b.p2-a.p1),k2=(b.p2-a.p2)*(b.p1-a.p2);
P p;
p.x=((a.p1.x)*k2+(a.p2.x)*k1)/(k1+k2);
p.y=((a.p1.y)*k2+(a.p2.y)*k1)/(k1+k2);
return p;
}
il bool jud(L a,L b,L t){//判断a和b的交点是不是在t内 ，在外部返回true
P p=inter(a,b);
return (t.p1-p)*(t.p2-p)<=0;
}
void hpi(){
sort(A+1,A+n+1);//极角排序
bot=0,top=-1;
for(int i=1;i<=n;i++){
if(i>1&&A[i].g==A[i-1].g) continue;
while(bot<top&&jud(q[top],q[top-1],A[i])) top--;
while(bot<top&&jud(q[bot],q[bot+1],A[i])) bot++;
q[++top]=A[i];
}
q[top+1]=q[bot],tot=0;
for(int i=bot;i<=top;i++)
vis[q[i].id]=1;
}
il void solve(){
for(int i=1;i<=n;i++) if(vis[i]) printf("%d ",i);
printf("\n");
}
bool ck(){
int ans=0;
A[n+1].p1=A[1].p1;
for(int i=1;i<=n;i++) ans+=A[i].p1*A[i+1].p1;
return ans>0;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
double x,y;
scanf("%lf%lf",&x,&y);
A[i]={{0,y},{1,x+y},x,i};
}
if(!ck()){
for(int i=1,j=n;i<j;i++,j--)
swap(A[i],A[j]);
}
hpi();solve();
return 0;
}