标签存档：计算几何

【题目地址】http://www.apio.olympiad.org/
【算法分析】
取4个点，可以推出：
如果是构成凸四边形的话，有两种取法会覆盖完4个点。
如果是构成凹四边形的话，有1种取法会覆盖完4个点。
不要说正方形、矩形。。。题目说明不会有点在外接圆上的。
然后设取4个点中，构成凸四边形的有P个，凹四边形有Q个。
那么P+Q=C(n,4)
然后最终答案ans=(2*P+Q)/C(n,3)+3。
至于求Q。那么就是枚举那个凹四边形中的中心点，然后将其平移至原点，
问题转化成：求N个点中取三个点，过原点的三角形有多少个？
这个是一个经典问题。可以参考这里来解决：
http://hi.baidu.com/edwardmj/blog/item/40751a1454c50414962b4367.html
【CODE】
#include #include #include #include #define next(j) ((j)==n?1:j+1)
using namespace std;
typedef long long lld;
const int N=1505;
struct Point{int x,y;}a[N],tt[N];
int n;
int xx1,xx2;
lld F[N],ans,FM,P,Q;

void input(){
scanf("%d",&n);
int i;
for (i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
}

inline int get_xx(Point p){
if (p.x>=0 && p.y>0) return 1;
if (p.x>0 && p.y<=0) return 2;
if (p.x<=0 && p.y<0) return 3;
return 4;
}

inline int cj(Point &p0,Point &p1,Point &p2){
lld res=(lld)(p1.x-p0.x)*(lld)(p2.y-p0.y)-(lld)(p1.y-p0.y)*(lld)(p2.x-p0.x);
if (res<0) return -1;
if (res==0) return 0;
return 1;
}

inline bool cmp(Point x,Point y){
xx1=get_xx(x),xx2=get_xx(y);
if (xx1!=xx2) return xx1 return cj(a[0],x,y)<0;
}

void solve(){
sort(a+1,a+1+n,cmp);
ans+=(lld)(n)*(n-1)*(n-2)/6;
lld total;
int i,j=1;
for (i=1;i<=n;i++){
if (i==j) j=next(j);
while (i!=next(j) && cj(a[0],a[i],a[next(j)])<0) j=next(j);
if (j else total=j-i;
ans-=total*(total-1)/2;
}
}

inline void swap(Point &X,Point &Y){Point tmp=X; X=Y; Y=tmp;}

void work(){
FM=(lld)(n)*(n-1)*(n-2)/6;
ans=0;
memcpy(tt,a,sizeof(tt));
int i,j;
n;
for (i=1;i<=n;i++){
for (j=1;j<=n;j++) a[j]=tt[j];
swap(a[n],a[i]);
for (j=1;j a[j].x-=a[n].x;
a[j].y-=a[n].y;
}
n–;
solve();
n++;
}
Q=ans;
P=(lld)(n)*(n-1)*(n-2)*(n-3)/24-Q;
ans=2*P+Q;
printf("%.3lfn",(double)ans/(double)(FM)+3);
}

int main(){
freopen("signaling.in","r",stdin);
freopen("signaling.out","w",stdout);
input();
work();
}

【题目大意】
给定N个二维平面上的点。
问他们取3个出来，过原点的三角形有多少个。
【算法分析】
先极角排序。
然后维护一个最长区间，使得区间中任意一个点对满足向量(O, i)和向量(O, j)的夹角【其它】
APIO最后一题的本质模型。
【CODE】
/*
ID:jie22221
TASK:tricount
LANG:C++
*/

#include #include #include #include using namespace std;
typedef long long lld;
const int N=100005;
int n;
struct Point{int x,y;}a[N];

void input(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
}

int get_xx(Point p){
if (p.x>=0 && p.y>0) return 1;
if (p.x>0 && p.y<=0) return 2;
if (p.x<=0 && p.y<0) return 3;
return 4;
}

int cj(Point p0,Point p1,Point p2){
lld res=(lld)(p1.x-p0.x)*(lld)(p2.y-p0.y)-(lld)(p1.y-p0.y)*(lld)(p2.x-p0.x);
if (res<0) return -1;
if (res==0) return 0;
return 1;
}

int cmp(const void *X,const void *Y){
Point x=*((Point*)X),y=*((Point*)Y);
int xx1=get_xx(x),xx2=get_xx(y);
if (xx1!=xx2) return xx1-xx2;
return cj(a[0],x,y);
}

void solve(){
lld ans=(lld)(n)*(n-1)*(n-2)/6,total;
int i,j=1;
for (i=1;i<=n;i++){
if (i==j) j=j%n+1;
while (i!=j%n+1 && cj(a[0],a[i],a[j%n+1])<0) j=j%n+1;
if (j else total=j-i;
ans-=total*(total-1)/2;
}
cout << ans << endl;
}

int main(){
freopen("tricount.in","r",stdin);
freopen("tricount.out","w",stdout);
input();
qsort(a+1,n,sizeof(Point),cmp);
solve();
}

【题目】

Description

在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P，在CD上的 移动速度为Q，在平面上的移动速度R。现在lxhgww想从A点走到D点，他想知道最少需要走多长时间

Input

输入数据第一行是4个整数，表示A和B的坐标，分别为Ax，Ay，Bx，By
第二行是4个整数，表示C和D的坐标，分别为Cx，Cy，Dx，Dy
第三行是3个整数，分别是P，Q，R

Output

输出数据为一行，表示lxhgww从A点走到D点的最短时间，保留到小数点后2位

Sample Input

0 0 0 100
100 0 100 100
2 2 1

Sample Output

136.60

Hint

对于100%的数据，1<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000
1<=P，Q，R<=10 【算法分析】
好吧，很容易得出路径应该是这样一种形式：
A->p1->p2->D
其中p1在线段AB上，p2在线段CD上。
然后感觉应该是都满足单峰性质的。
表示不会证明。。。只是感觉。
可以用r1 * AB向量和r2 * DC向量分别表示p1、p2。

第一种：
嵌套二分r1和r2。得到速度非常快的一个算法。

第二种：
如果不放心，那么枚举r1，精度卡一下，卡1e-5之类。
然后二分r2。
得到一个比较快的算法。

第三种：
如果还不放心，那么直接暴力它吧。经测试，直接枚举r1和r2，卡精度2e-4，可以在每个测试数据1.8s的情况下暴力AC！
果然，很黄很暴力~

【其他】
我是傻X，因为求的是最小值，而不是最大值。
一开始二分的部分应该l=mid的时候写成r=mid
应该r=mid的时候写成了l=mid。
导致以为不符合单峰性质，所以有了各种暴力尝试。。。

【CODE1】
#include #include #include #include #include using namespace std;
const double eps=1e-6;
int Ax,Ay,Bx,By,Cx,Cy,Dx,Dy,Rab,Rcd,R;
double xx1,yy1,xx2,yy2,d1,d2,d3,r1;

inline double dis(double x1,double y1,double x2,double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

inline double Get(double r2){
xx1=(Bx-Ax)*r1+Ax;
yy1=(By-Ay)*r1+Ay;
xx2=(Cx-Dx)*r2+Dx;
yy2=(Cy-Dy)*r2+Dy;
d1=dis(xx1,yy1,Ax,Ay)/Rab;
d2=dis(xx1,yy1,xx2,yy2)/R;
d3=dis(xx2,yy2,Dx,Dy)/Rcd;
return d1+d2+d3;
}

double solve(double tmp){
r1=tmp;
double l=0,r=1,mid;
while (l+eps mid=(l+r)/2;
if (Get(mid) else l=mid;
}
return Get(l);
}

int main(){
cin>>Ax>>Ay>>Bx>>By>>Cx>>Cy>>Dx>>Dy>>Rab>>Rcd>>R;
double l=0,r=1,mid;
while (l+eps mid=(l+r)/2;
if (solve(mid) else l=mid;
}
printf("%.2lfn",solve(l));
}
【CODE2】
#include #include #include #include #include using namespace std;
const double eps=1e-5;
int Ax,Ay,Bx,By,Cx,Cy,Dx,Dy,Rab,Rcd,R;
double xx1,yy1,xx2,yy2,d1,d2,d3,r1;

inline double dis(double x1,double y1,double x2,double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

inline double Get(double r2){
xx1=(Bx-Ax)*r1+Ax;
yy1=(By-Ay)*r1+Ay;
xx2=(Cx-Dx)*r2+Dx;
yy2=(Cy-Dy)*r2+Dy;
d1=dis(xx1,yy1,Ax,Ay)/Rab;
d2=dis(xx1,yy1,xx2,yy2)/R;
d3=dis(xx2,yy2,Dx,Dy)/Rcd;
return d1+d2+d3;
}

double solve(double tmp){
r1=tmp;
double l=0,r=1,mid;
while (l+eps mid=(l+r)/2;
if (Get(mid) else l=mid;
}
return Get(l);
}

int main(){
cin>>Ax>>Ay>>Bx>>By>>Cx>>Cy>>Dx>>Dy>>Rab>>Rcd>>R;
double i=0,ans=1e20;
for (i=0;i<1;i+=eps)
ans=min(ans,solve(i));
printf("%.2lfn",ans);
}
【CODE3】
#include #include #include #include #include using namespace std;
const double eps=1e-6;
const double eps2=1e-7;
const double eeps=2e-4;
int Ax,Ay,Bx,By,Cx,Cy,Dx,Dy,Rab,Rcd,R;

inline double dis(double x1,double y1,double x2,double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

inline double Get(double r1,double r2){
double x1,y1,x2,y2,d1,d2,d3;
x1=(Bx-Ax)*r1+Ax;
y1=(By-Ay)*r1+Ay;
x2=(Cx-Dx)*r2+Dx;
y2=(Cy-Dy)*r2+Dy;
d1=dis(x1,y1,Ax,Ay)/Rab;
d2=dis(x1,y1,x2,y2)/R;
d3=dis(x2,y2,Dx,Dy)/Rcd;
return d1+d2+d3;
}

double solve(double r1){
double l,ans=1e20;
for (l=0;l<1;l+=eeps) ans=min(ans,Get(r1,l));
return ans;
}

int main(){
cin>>Ax>>Ay>>Bx>>By>>Cx>>Cy>>Dx>>Dy>>Rab>>Rcd>>R;
double l=0,r=1,mid,ans=1e20;
for (l=0;l<1;l+=eeps) ans=min(ans,solve(l));
printf("%.2lfn",ans);
}

【题目地址】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1132
【解题经历】
先YM LCC大牛。。。
表示一直不会极角排序，做凸包我都是用按Y坐标排，然后弄上壳和下壳的那种。。。
然后YY了比较久，感觉很难。。。。
于是去围观LCC大牛的代码，OH。。。原来这么简单。
【算法分析】
实际上我之前想的都陷入了一个误区，那就是原点是任意的，而LCC大牛的代码中是取左上角的那个点做原点，那么所有的点都会在同一象限，那么直接用叉积就可以判断了（因为角度都0<=α<=π/2，叉积不会出现分两边的问题）。
现在看这道题，假设枚举一个点k，那么ans+=SUM(abs(Xi*Yj-Yi*Xj)) (1<=i然后我们对于点i，所要加的面积应该是Xi*((Yi+1) + (Yi+2) +….+ (Yn))  -  Yi*((Xi+1) + (Xi+2) + … + (Xn))。
好吧，维护和就可以。
然后要注意的是，极角排序是选定了左上角那个点的，然后每次都去掉这个基准点就可以不断进行，且没有重复，使得最后剩下<3个点，就是结果了。
【其他】。。。时间排最后几位，表示不明真相，为啥LCC大牛这么快呢。。。55555
【CODE】
#include using namespace std;
typedef __int64 lld;
const int N=3005;
int n;
struct Point{lld x,y;}P[N];
lld ans=0;

void input(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%I64d%I64d",&P[i].x,&P[i].y);
}

bool cmp(Point a,Point b){return a.x*b.yvoid count(int n){
lld Sx=0,Sy=0,i,k=1,S;
for (i=1;i<=n;i++)
if (P[i].x swap(P[k],P[n]);
for (i=1;i P[i].x-=P[n].x;
P[i].y-=P[n].y;
}
sort(P+1,P+n,cmp);
for (i=1;i ans+=P[i].x*Sy-P[i].y*Sx;
Sx+=P[i].x;
Sy+=P[i].y;
}
}

int main(){
input();
for (int i=n;i>=1;i–) count(i);
if (ans%2==1) printf("%I64d.5n",ans/2);
else printf("%I64d.0n",ans/2);
}

【题目大意】

给定两个圆心，两圆的面积和，以及N个点的坐标。给出最小有多少个点不能覆盖到。

【算法分析】

枚举“卡住”第一个圆的是哪个点，然后把剩下的面积分到另外一个圆去。

【其它】注意，第一个圆的半径可以为0….比赛的时候就因为这个没A

【CODE】

#include #include #include #include #include #define sqr(x) ((x)*(x))
using namespace std;
const double pi=3.141;
const double eps=1e-8;
const int N=1111;
int n;
double lx[N],ly[N],sum,s1,s2,r1,r2;

inline double dis(int i,int j){
    return sqr(lx[i]-lx[j])+sqr(ly[i]-ly[j]);
}   

int main(){
    int Tc=0,now,ans;
    for (;;){
        scanf("%d",&n);
        if (!n) break;
        Tc++; ans=0;
        scanf("%lf%lf%lf%lf%lf",&lx[n+1],&ly[n+1],&lx[n+2],&ly[n+2],&sum);
        for (int i=1;i<=n;i++) scanf("%lf%lf",&lx[i],&ly[i]);
        for (int i=1;i<=n+1;i++){
            r1=dis(i,n+1);
            s1=r1*pi;
            if (s1>sum+eps) continue;
            s2=sum-s1+eps;
            r2=s2/pi;
            now=0;
            for (int j=1;j<=n;j++)
              if (dis(j,n+1)<=r1+eps || dis(j,n+2)<=r2+eps) now++;
            ans=max(now,ans);
        }   
        cout << Tc << ". " << n-ans << endl;
    }   
}