计算几何

首先要会套模板

旋转卡壳资料:http://www.cnblogs.com/Booble/archive/2011/04/03/2004865.html

求最大三角形
SPOJ - MTRIAREA

#include<iostream>
#include<algorithm>
#include<cstdio> 
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 1e5;
struct point{
    int x,y;
}p[maxn];
int dis(point a,point b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int cross(point p0,point p1,point p2){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
bool cmp1(point p1,point p2){
    return p1.x<p2.x||(p1.x==p2.x&&p1.y<p2.y);
}
bool cmp2(point p1,point p2){
    int c = cross(p[0],p1,p2);
    if(c==0) return dis(p[0],p1)<dis(p[0],p2);
    return c>0;
}
point sta[maxn];
int top,n;
void convex(int n){
    top=0;
    sort(p,p+n,cmp1);
    sort(p+1,p+n,cmp2);
    sta[top++]=p[0];
    sta[top++]=p[1];
    for(int i = 2; i < n; i++){
        if(cross(sta[top-2],sta[top-1],p[i])>0) sta[top++]=p[i];
        else{
            top--;
            while(top>=2&&cross(sta[top-2],sta[top-1],p[i])<=0) top--;
            sta[top++]=p[i];
        }
    }
}
double rotating(int n){
    int j=1,k=0;
    double ans=0;
    for(int i=0;i<n;i++){
        j=(i+1)%n;
        k=(j+1)%n;
        while(fabs(cross(sta[i],sta[j],sta[k]))<fabs(cross(sta[i],sta[j],sta[(k+1)%n])))
            k=(k+1)%n;
        while(j!=i&&k!=i){
            ans=max(ans,fabs(cross(sta[i],sta[j],sta[k])));
            while(fabs(cross(sta[i],sta[j],sta[k]))<fabs(cross(sta[i],sta[j],sta[(k+1)%n])))
                k=(k+1)%n;
            j=(j+1)%n;
        }
    }
    return ans*0.5;
}

int main(){
    while(scanf("%d",&n)!=EOF){
        if(n==-1) break;
        for(int i = 0; i < n; i++) scanf("%d%d",&p[i].x,&p[i].y);
        convex(n);
        double ans = rotating(top);
        printf("%.2lf\n",ans);
    }
    return 0;
}

三分法求非单调函数
HDU2899

    #include <cstdio>  
    #include <iostream>  
    #include <algorithm>  
    using namespace std;  
      
    double y;  
    double val(double x){  
        return 6*x*x*x*x*x*x*x+8*x*x*x*x*x*x+7*x*x*x+5*x*x-y*x;  
    }  
      
    double solve(double l,double r){  
        double eps = 1e-7;  
        while(l + eps < r){  
            double lmid = l + (r-l)/3,rmid = r - (r-l)/3;  
            if(val(lmid) < val(rmid)){  
                r = rmid;  
            }else{  
                l = lmid;  
            }  
        }  
        return val(l);  
    }  
    int main(){  
        int t;  
        cin>>t;  
        while(t--){  
            cin>>y;  
            printf("%.4f\n", solve(0,100.0));  
        }  
        return 0;  
    }  

进阶
HDU2438

#include <stdio.h>
#include <string>
#include<iostream>
#include <cstring>
#include <iomanip>
#include <cmath>
#define pi 3.1415926
#include <algorithm>
using namespace std;    
double x,l,y,w,a,b,c;
double f(double t);
int main(){
    while(cin>>x>>y>>l>>w)
    {   a=0.0;
        b=pi/2.0;
        double mid,mmid;
        while(b-a>1e-10){
           mid=(a+a+b)/3.0;//rmid
           mmid=(mid+2*b)/3.0;//lmid
           if(f(mid)>f(mmid))
               b=mmid;
           else
               a=mid;    
        }
        if(f(a)>y)
            cout<<"no"<<endl;
        else cout<<"yes"<<endl;        
    }
    return 0;
} 
double f(double t){
    return l*cos(t)+(w-x*cos(t))/(sin(t));
}

lm低于rm,则极大在[ lm,right ](为啥不是[ left, rm ]?你试试把rm放在lm右边,极大值左边看看?),否则极大在 [ left, rm ]。写代码上就是极小的处理语句反过来就行了。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int n,m,f[202];
struct node{
    int x,y,w;
 }e[1001];
int cmp(node a,node b)
{
    return a.w>b.w;
}
int find(int x)
{
    if(f[x]!=x)
    f[x]=find(f[x]);
    return f[x];
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int i,j,k,t;
        for(i=0;i<m;i++)
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
        sort(e,e+m,cmp);
        scanf("%d",&t);
        while(t--)
        {
            int a,b,min=1000001;
            scanf("%d%d",&a,&b);
            for(i=0;i<m;i++)
            {
                for(j=1;j<=n;j++)
                f[j]=j;
                for(j=i;j<m;j++)
                {
                    int aa,bb;
                    aa=find(e[j].x);
                    bb=find(e[j].y);
                    if(aa!=bb)
                    f[aa]=bb;
                    if(find(a)==find(b))
                    {
                        min=(e[i].w-e[j].w)<min?(e[i].w-e[j].w):min;
                        break;
                    }
                    
                }
            }
            if(min==1000001)
            printf("-1\n");
            else
            printf("%d\n",min);
        }
    }
    return 0;
}

Pick定理:S=I+E/2-1 (E表示格点多边形边上的点,I表示格点多边形内的点)

Pick推论:格点多边形S=0.5k (k是正整数)

边上格点数公式:线段(x1,y1)-(x2,y2)的格点数=gcd(abs(x1-x2),abs(y1-y2))+1


感觉这里知识点比较多,在网上搜了汇编的待刷题集
FOJ

Hotter Colder

求线段的中位线,线段相交求交点,求凸多边形的面积,

无归之室

本题精度要求非常高,用三角函数的话,很容易就wa..

Reflections

求一条射线遇到圆后的反射光,

即圆和直线求交点,求点关于交点法线的对称点。

Pipe http://acm.fzu.edu.cn/problem.php?pid=1088

求一条光线从管道口进入,最远能达到多远。

判断线段左右位置关系,求线段相交交点。

A Pilot in Danger!

判断点在区域内

Area in Triangle

在三角形内的气球膨胀,求膨胀后的面积。

分情况推公式

Triangle

在给定的n( 1<=n<=50000)个点中,取3个点组成三角形,求面积最大。

显然这3个点在凸包上,点集凸包化+凸包上的点k^2(原来要k^3的,利用某些性质剪枝,降到k^2).

Area

Pick定理

Center of Gravity

已知半径,角度的扇形,求其重心到圆心的距离。

Stone

求多边形的重心

Surround the Trees

凸包

Star not a Tree? http://acm.fzu.edu.cn/problem.php?pid=1355

费马点

Coplanar Points

利用差积判断4点共面。

长方形的并的面积

离散化

Common Area

三角形和圆的共同面积。

弹弓

n(1<=n<=700)个点中,最多有多少个点在同一条直线上。

牧场

n(2<=n<=100)个点中,取其中部分点组成的一个凸多边形,求这样的凸多边形的最大顶点数. Oaiei's Trouble http://acm.fzu.edu.cn/problem.php?pid=1510

图形学中的直线剪裁算法,可以用计算几何中的点和线段的关系,线段和线段的求交点来求解。

Defense the country

Treasure Hunt http://acm.fzu.edu.cn/problem.php?pid=1332

线段相交

Minkowski Sum

Area Ratio

求三角形的内切圆,外接圆

Video Surveillance 简单题

最大可分离值问题

POJ

1031 Fence

1039 Pipe

1092 Farmland

1106 Transmitters

1113 Wall

1118 Lining Up

1133 Stars

1151 Atlantis

1225 STRICTLY INSCRIBED SIMILAR TRIANGLES 1259 The Picnic

1263 Reflections

1265 Area

1266 Cover an Arc.

1269 Intersecting Lines

1271 Nice Milk

1279 Art Gallery

1294 Not Too Convex Hull

1319 Pipe Fitters

1347 Triangle

1361 JaWs

1375 Intervals

1379 Run Away

1389 Area of Simple Polygons

1408 Fishnet

1410 Intersection

1418 Viva Confetti

1428 Hermes' Colony

1434 Fill the Cisterns!

1444 Parallelepiped walk

1471 Triangles

1473 There's Treasure Everywhere!

1494 Sunrise

1499 Supercomputer Selection, The Sequel

1500 Polygonal Puzzle

1514 Metal Cutting

1518 Problem Bee

1536 Trains

1556 The Doors

1569 Myacm Triangles

1584 A Round Peg in a Ground Hole

1586 Three Sides Make a Triangle

1605 Horse Shoe Scoring

1610 Quad Trees

1623 Squadtrees

1624 This Takes the Cake

1645 BSP Trees

1654 Area

1660 Princess FroG

1673 EXOCENTER OF A TRIANGLE 1685 Color Tunnels

1687 Buggy Sat

1688 Dolphin Pool

1693 Counting Rectangles

1696 Space Ant

1727 Advanced Causal Measurements (ACM) 1758 Frontier

1765 November Rain

1774 Fold Paper Strips

1803 Box Art

1810 Covering

1813 Overlapped Shapes

1819 Disks

1834 线段处理

1843 Shire

1851 Map

1871 Bullet Hole

1873 The Fortified Forest

1875 Robot

1877 Flooded!

1881 Sail Race

1899 Farmer Bill's Problem

1902 Illumination

1912 A highway and the seven dwarfs

1921 Paper Cut

1927 Area in Triangle

1931 Biometrics

1937 Balanced Food

1939 Diplomatic License

1940 Polygon Programming with Ease

1956 Pumps and Pipes

1971 Parallelogram Counting

1981 Circle and Points

1982 Water Tank

2007 Scrambled Polygon

2012 Triangle Cuts

2016 Ink Blots

2026 As the Crow Flies

2031 Building a Space Station

2036 I Conduit!

2043 Area of Polygons

2048 Monster Trap

2053 Square

2066 Minimax Triangulation

2069 Super Star

2074 Line of Sight

2079 Triangle

2087 Petanque

2098 Ellipse

2130 Jogging

2149 Inherit the Spheres

2150 Crossing Prisms

2164 Find the Border

2165 Gunman

2172 Bricks

2177 Ghost Busters

2284 That Nice Euler Circuit

2621 Parallelepiped

2622 Convex hull

2686 Traveling by Stagecoach

2687 Earth Observation with a Mobile Robot Team 2747 Shy Polygons

2839 Convex Hull and Triangle

2932 Coneology

2954 Triangle

3011 Secrets in Shadows

3129 How I Wonder What You Are!

3130 How I Mathematician Wonder What You Are! 3135 Polygons on the Grid

3334 Connected Gheeves

3335 Rotating Scoreboard

3347 Kadj Squares

3384 Feng Shui
3407Brookebonds'envaengu;zoj相关练习题;159716081648168319102102;2015(中欧1999正赛)2107(浙江200;2214(北京2004正赛题,费马点,知道该知识;主要内容(仔细核对,看看自己哪些未掌握):;判断线段相交;判断直线相交;;判断点是否在多边形内;求凸包;;凸多边形面积计算;矩形的交与并(扫描

3407 Brookebond s'en va en guerre... 3410 Split convex polygon 3608 Bridge Across Islands ZOJ

zoj相关练习题

1597 1608 1648 1683 1910 2102 2157 2318 2335 2347 2352 2361 2370 2375 2403

2015(中欧1999正赛) 2107(浙江2004省赛) 2228(北京2004预赛题,难) 2234(北京2004预赛题)

2214(北京2004正赛题,费马点,知道该知识点=〉易解,否则=〉不可能) 2394(上海2004正赛题)

主要内容(仔细核对,看看自己哪些未掌握):

判断线段相交; 判断直线相交;

判断点是否在多边形内; 求凸包;

凸多边形面积计算; 矩形的交与并(扫描法);

已知三点求三角形面积(包括海伦公式)和重心; 已知三点求外接圆和内接圆圆心、半径、面积 ; 最近点对问题;

最远点对问题;

点集或图形集合的最小覆盖圆; 点集或图形集合的最小覆盖矩形; 三角剖分; 费尔马点的计算;

标签: 算法, 学习

添加新评论