标签存档：计算几何

【题目链接】http://ace.delos.com/ioiupload?init=1&a=uNRSh9JKRlk
【题目大意】
给定n<=300个形如ax+by+cz>=0的不等式。(将<=0的乘一个 -1来改变不等号方向)
求在其满足的前提下，给出m个询问，
看能不能确定另外给出的式子ax+by+cz是>0还是<0还是无法确定。
它很猥琐的还有常量条件。
x>0
y>0
z>0
x<=100y
x<=100z
y<=100x
y<=100z
z<=100x
z<=100y
就这么多。
【算法分析】
由于x,y,z>0，所以我们将不等式两边同除以z，不用变号。
那么不等式变成：a(x/z)+b(x/z)+c>=0
我们令X=x/z,Y=x/z。
那么不等式变为aX+bY+c>=0。
然后？
半平面交！
就是先对给出的条件全部变为这种限制，然后求出其半平面交。
然后这个半平面交的算法是我自己YY出来的,O(n^2)。。。小有成就感。
当然，众神牛估计要笑而不语了。
好了，半平面交完以后呢，就只要对每个给出的限制转化为直线。然后看这个直线是“穿过”这个半平面交。
如果穿过，表示两边的取值都可能，所以不能确定他的不等号方向。
否则，看就看它在哪一边就行了。
【其它】
好有好多好多小细节。。。然后我写成的程序，精度要卡得刚好才能过= =
如果要学习半平面交的话。。。还是别看我这。因为写得实在太水，太长了。
我看过师傅的模板，不禁为其短小精悍而叹服。
但是毕竟是自己推得算法。。。再水也是自己的= =
【CODE】
/*
ID:jie22221
TASK:starc
LANG:C++
*/
#include #include #include #include #define N 355
#define INF 100
#define eps 1e-6
#define seps 1e-2
using namespace std;
struct Line{double a,b,c;}LL[N];
struct Point{double x,y;}p[N*N],tp[N*N];
int n,Ln,m,tn;

void init(){
int i,A1,B1,C1,A2,B2,C2;
char ch;
cin >> Ln >> m;
for (i=1;i<=Ln;i++){
cin >> ch >> A1 >> B1 >> C1 >> A2 >> B2 >> C2;
if (ch==’J’){
LL[i].a=A1-A2;
LL[i].b=B1-B2;
LL[i].c=C1-C2;
}else{
LL[i].a=A2-A1;
LL[i].b=B2-B1;
LL[i].c=C2-C1;
}
}
Ln++;
LL[Ln].a=-1;
LL[Ln].b=100;
LL[Ln].c=0;
Ln++;
LL[Ln].a=100;
LL[Ln].b=-1;
LL[Ln].c=0;
n=4;
p[1].x=seps; p[1].y=seps;
p[2].x=INF; p[2].y=seps;
p[3].x=INF; p[3].y=INF;
p[4].x=seps; p[4].y=INF;
}

inline double f(Line L,Point pp){
return L.a*pp.x+L.b*pp.y+L.c;
}
inline double cj(Point A,Point B){return A.x*B.y-A.y*B.x;}
inline void dec(int &x){x–; if (x<1) x=n;}
inline void inc(int &x){x++; if (x>n) x=1;}

Line Get_Line(Point A,Point B){
Line res;
res.a=A.y-B.y;
res.b=B.x-A.x;
res.c=cj(A,B);
return res;
}

Point Cross_Point(Line A,Line B){
Point res;
res.x=(B.b*A.c-A.b*B.c)/(B.a*A.b-A.a*B.b);
res.y=(B.a*A.c-A.a*B.c)/(A.a*B.b-B.a*A.b);
return res;
}

double fabs(double x){
if (x<0) return -x;
return x;
}

void Cut(Line L){
int i,j,k,st=1;
bool flag=false;
for (i=1;i<=n;i++)
if (f(L,p[i])<-eps) flag=true;
if (!flag){
for (i=1;i<=n;i++) tp[i]=p[i];
tn=n;
return;
}
while (f(L,p[st])<-eps) st++;
for (i=st;;inc(i))
if (f(L,p[i])<-eps) break;
for (j=st;;dec(j))
if (f(L,p[j])<-eps) break;
tn=0;
for (k=j%n+1;k!=i;inc(k))
tp[++tn]=p[k];
dec(i);
if (fabs(f(L,tp[tn]))>eps){
Line tmp=Get_Line(p[i],p[i%n+1]);
tp[++tn]=Cross_Point(tmp,L);
}
if (fabs(f(L,tp[ 1]))>eps){
Line tmp=Get_Line(p[j],p[j%n+1]);
tp[++tn]=Cross_Point(tmp,L);
}
}

void half_plane(){
int i,j;
for (i=1;i<=Ln;i++){
Cut(LL[i]);
for (j=1;j<=tn;j++) p[j]=tp[j];
n=tn;
}
}

void solve(){
int A1,B1,C1,A2,B2,C2,t1,t2,i,j;
for (i=1;i<=m;i++){
t1=t2=0;
cin >> A1 >> B1 >> C1 >> A2 >> B2 >> C2;
Line L;
L.a=A1-A2;
L.b=B1-B2;
L.c=C1-C2;
for (j=1;j<=n;j++){
if (f(L,p[j])<-1e-8) t1++;
if (f(L,p[j])> 1e-8) t2++;
}
if (t1==0 && t2==0 || t1+t2!=n) puts("U"); else
if (!t1) puts("J"); else
if (!t2) puts("B"); else
puts("U");
}
}

int main(){
freopen("starc.in","r",stdin);
freopen("starc.out","w",stdout);
ios::sync_with_stdio(false);
init();
half_plane();
solve();
return 0;
}

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1941
【题目大意】
给出平面上n个点。设Ki表示离i这个点的最远点的距离，与离i这个点的最近点的距离之差。
那么题目就要你求Min(Ki)。
所有距离均为哈密顿距离。
【算法分析】
首先如果我们把一个点作为原点。
那么我们发现哈密顿距离为<=2的是这个形状：
..*..
.***.
*****
.***.
..*..
我们把中间那个当原点，那么我们分开4个象限来YY。
假如说第二象限吧，
显然，哈密顿距离为2的点都在一条直线上，在这之后，哈密顿距离为3的点也都会在一条直线上~。而这条直线的倾斜角都是45°
在这直线上的点都可以表示成x-y=q。q为一个常数。（就是y=kx+b的-b啦。。。）
然后我们可以把一个点的权置为x-y。
先按x坐标从小到大排序，然后搞过来，然后要处理第二象限的话，就是在前面的点里，找y坐标>yi的点里面，x-y最小(大)的。然后这个可以用树状数组解决。
然后其它象限也是类似解决。不过1、3象限是要用倾斜角135°的直线去弄。
【其它】1A，Orz，我承认我用了外挂。。。
1 27780 edward_mj 2856K 1653MS G++ 3.30K 2010-06-04 10:19:22 2 26574 Soiliml 6488K 2386MS Pascal 4.60K 2010-05-28 21:43:28 3 25994 root 2880K 2482MS G++ 2.41K 2010-05-26 19:44:01 4 26188 hyf042 15928K 3185MS G++ 4.51K 2010-05-27 12:56:02 5 26410 jiakai 11128K 4012MS G++ 6.46K 2010-05-28 08:05:09 6 26408 jiakai 11128K 4013MS G++ 6.84K 2010-05-28 08:02:40 7 27723 michael_wind 7696K 4294MS Pascal 4.33K 2010-06-03 21:23:23 8 26405 jiakai 6008K 4310MS G++ 6.13K 2010-05-28 07:57:36 9 26845 zxytim 16184K 4325MS G++ 5.08K 2010-05-30 16:08:56 10 26406 jiakai 6008K 4340MS G++ 6.13K 2010-05-28 07:58:00 11 26209 sonicmisora 16320K 4467MS G++ 4.06K 2010-05-27 14:31:16 12 26208 sonicmisora 16320K 4467MS G++ 5.03K 2010-05-27 14:29:47 13 25996 root 8632K 4560MS G++ 3.03K 2010-05-26 19:44:52 14 26411 zxytim 6396K 4684MS G++ 4.81K 2010-05-28 08:25:29 【CODE】
#include #include #include const int N=500005;
const int INF=0x7FFFFFFF/2-79;
int n;
int ly[N],Qmin[N],Qmax[N];
struct Point{int x,y,max,min;}a[N];

void Read(int &x){
char ch=getchar();
while (!(ch>=’0′ && ch<='9')) ch=getchar();
x=0;
while (ch>=’0′ && ch<='9'){
x=x*10+ch-‘0’;
ch=getchar();
}
}

void input(){
Read(n);
int i;
for (i=1;i<=n;i++){
Read(a[i].x);
Read(a[i].y);
}
for (i=1;i<=n;i++){
a[i].max=-INF;
a[i].min=INF;
}
}

void clr(){
for (int i=1;i<=n;i++){
Qmin[i]=INF;
Qmax[i]=-INF;
}
}

int cmp(const void *A,const void *B){return *((int*)A)-*((int*)B);}
void Lisan(){
for (int i=1;i<=n;i++) ly[i]=a[i].y;
qsort(ly+1,n,sizeof(int),cmp);
}

int Findy(int x){
int l=1,r=n,mid;
while (l mid=(l+r)/2;
if (x>ly[mid]) l=mid+1;
else r=mid;
}
return l;
}

int Getmax(int p){
int res=-INF;
for (int i=p;i;i-=i&-i)
res>?=Qmax[i];
return res;
}

int Getmin(int p){
int res=INF;
for (int i=p;i;i-=i&-i)
res return res;
}

void Insmax(int p,int key){
for (int i=p;i<=n;i+=i&-i)
Qmax[i]>?=key;
}

void Insmin(int p,int key){
for (int i=p;i<=n;i+=i&-i)
Qmin[i]}

inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x if (((Point*)A)->x!=((Point*)B)->x) return ((Point*)A)->x – ((Point*)B)->x;
return ((Point*)B)->y-((Point*)A)->y;
}

void Deal_45(){
int i,y;
qsort(a+1,n,sizeof(Point),cmp45);
clr();
for (i=1;i<=n;i++){
y=n-Findy(a[i].y)+1;
a[i].max=max(a[i].max,a[i].x-a[i].y-Getmin(y));
a[i].min=min(a[i].min,a[i].x-a[i].y-Getmax(y));
Insmax(y,a[i].x-a[i].y);
Insmin(y,a[i].x-a[i].y);
}
clr();
for (i=n;i>=1;i–){
y=Findy(a[i].y);
a[i].max=max(a[i].max,Getmax(y)-(a[i].x-a[i].y));
a[i].min=min(a[i].min,Getmin(y)-(a[i].x-a[i].y));
Insmax(y,a[i].x-a[i].y);
Insmin(y,a[i].x-a[i].y);
}
}

int cmp135(const void *A,const void *B){
if (((Point*)A)->x!=((Point*)B)->x) return ((Point*)A)->x – ((Point*)B)->x;
return ((Point*)A)->y-((Point*)B)->y;
}

void Deal_135(){
int i,y;
qsort(a+1,n,sizeof(Point),cmp135);
clr();
for (i=1;i<=n;i++){
y=Findy(a[i].y);
a[i].max=max(a[i].max,a[i].x+a[i].y-Getmin(y));
a[i].min=min(a[i].min,a[i].x+a[i].y-Getmax(y));
Insmax(y,a[i].x+a[i].y);
Insmin(y,a[i].x+a[i].y);
}
clr();
for (i=n;i>=1;i–){
y=n-Findy(a[i].y)+1;
a[i].max=max(a[i].max,Getmax(y)-(a[i].x+a[i].y));
a[i].min=min(a[i].min,Getmin(y)-(a[i].x+a[i].y));
Insmax(y,a[i].x+a[i].y);
Insmin(y,a[i].x+a[i].y);
}
}

void work(){
Deal_45();
Deal_135();
}

void output(){
int res=INF;
for (int i=1;i<=n;i++)
res printf("%dn",res);
}

int main(){
input();
Lisan();
work();
output();
return 0;
}

【题目链接】http://acm.fzu.edu.cn/problem.php?pid=1904
【题目大意】
师傅买了一个矩形的大蛋糕，切了N刀，问这个大蛋糕剩下的块里最大的一块有多大?
【算法分析】
首先最直接的方法：
DFS每刀的直线方程>=0还是<=0，然后求半平面交。
第二种方法：
DFS每刀的直线方程>=0还是<=0，然后再枚举所有直线的交点中在这个半平面内的。
对这些点做凸包，然后算面积。
【其它】
我是傻×。。。居然WA了一遍。
AC的：
printf("Case #%d: %.3lfn",i,ans);
WA的：
printf("Case #%d: %.3lfn",Tc,ans);
样例都不过就拿去交了= =。。。。。
【CODE】
#include #include #include #include #define AA ((Point*)A)
#define BB ((Point*)B)
const int N=30;
const double eps=1e-6;
int n,pn,plt,Lt,List[N*N];
double ans,S;
struct Line{int a,b,c;}L[N];
struct Point{double x,y;}P[N*N],pl[N*N];

void Add_Line(int i,int x1,int y1,int x2,int y2){
L[i].a=y1-y2;
L[i].b=x2-x1;
L[i].c=x1*y2-x2*y1;
}

void Add_Point(Line A,Line B){
int tmp=A.a*B.b-B.a*A.b;
if (!tmp) return;
pn++;
P[pn].x=(double)(A.b*B.c-B.b*A.c)/tmp;
P[pn].y=(double)(B.a*A.c-A.a*B.c)/tmp;
}

void input(){
scanf("%d",&n);
for (int i=0;i int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
Add_Line(i,x1,y1,x2,y2);
}
Add_Line(n,0,100,0,0);
Add_Line(n+1,0,0,100,0);
Add_Line(n+2,100,0,100,100);
Add_Line(n+3,100,100,0,100);
pn=0;
for (int i=0;i for (int j=i+1;j Add_Point(L[i],L[j]);
P[N*N-1].x=0;
P[N*N-1].y=0;
}

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

bool In_Line(Point pp,Line ll){
double res=pp.x*ll.a+pp.y*ll.b+ll.c;
if (fabs(res) if (res>=0) return true;
return false;
}

void swap(Point &A,Point &B){
Point tmp=A;
A=B;
B=tmp;
}

int cmp(const void *A,const void *B){
return cj(P[N*N-1],*AA,*BB);
}

void TB(){
if (plt<3) return;
Point m;
int maxi=0;
m.x=1e50;
for (int i=1;i<=plt;i++)
if (pl[i].x m=pl[i];
maxi=i;
}
for (int i=1;i<=plt;i++){
pl[i].x-=m.x;
pl[i].y-=m.y;
}
swap(pl[1],pl[maxi]);
qsort(pl+2,plt-1,sizeof(Point),cmp);
pl[plt+1]=pl[1];
Lt=1; List[1]=1;
for (int i=2;i<=plt+1;i++){
while (Lt>1 && cj(pl[List[Lt-1]],pl[i],pl[List[Lt]])<=0) Lt--;
List[++Lt]=i;
}
}

void Count(){
S=0;
if (plt<3) return;
for (int i=1;i Point &pre=pl[List[i]],&now=pl[List[i+1]];
S+=pre.x*now.y-pre.y*now.x;
}
S=fabs(S)/2;
}

void Try(){
int i,j;
plt=0;
for (i=1;i<=pn;i++){
bool flag=true;
for (j=0;j if (!In_Line(P[i],L[j])){
flag=false;
break;
}
if (flag) pl[++plt]=P[i];
}
TB();
Count();
if (S>ans) ans=S;
}

void dfs(int depth){
if (depth==n) {Try(); return;}
dfs(depth+1);
L[depth].a=-L[depth].a;
L[depth].b=-L[depth].b;
L[depth].c=-L[depth].c;
dfs(depth+1);
L[depth].a=-L[depth].a;
L[depth].b=-L[depth].b;
L[depth].c=-L[depth].c;
}

int main(){
freopen("1904.in","r",stdin);
freopen("1904.out","w",stdout);
int Tc,i;
scanf("%d",&Tc);
for (i=1;i<=Tc;i++){
input();
ans=0;
dfs(0);
printf("Case #%d: %.3lfn",i,ans);
}
}

【题目大意】
空间坐标系中(x,y,z)中：
给出一个射线和N个点。
求出和这个射线最远的点和射线的距离是多少。
【算法分析】
首先围观一下点到直线的距离怎么搞？
+_+。。。直接弄垂线不好搞啊。
于是弄一个三角形面积。再除以底边的长度，就可以得到高了。
面积可以用海伦公式。这样就什么都不需要了，只需要点与点之间的长度计算。

然后再YY一下射线，如果是高飘出射线，那个特定的角就会变钝角。（划一下就可以知道哪个角）
然后利用勾股定理a^2+b^2#include #include #include #include const int N=100005;
struct Point{int x,y,z;}pl[N],p1,p2;
int n;
double ans;

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

inline double Sqr(double x){return x*x;}
inline double max(double x,double y){
if (x>y) return x;
else return y;
}
inline double min(double x,double y){
if (x else return y;
}

inline double dis(Point A,Point B){
return sqrt(Sqr(A.x-B.x)+Sqr(A.y-B.y)+Sqr(A.z-B.z));
}

inline void swap(double &x,double &y){
double tmp=x; x=y; y=tmp;
}

inline bool DunJiao(double a,double b,double c){
if (Sqr(a)+Sqr(b) return false;
}

void solve(){
int i,j,k;
double p,S,a,b,c,now;
ans=0;
for (i=1;i<=n;i++){
a=dis(p1,pl[i]); b=dis(p1,p2); c=dis(p2,pl[i]);
p=0.5*(a+b+c);
S=sqrt(p*(p-a)*(p-b)*(p-c));
now=min(a,c);
if (!DunJiao(a,b,c))
now=min(now,S*2/b);
ans=max(ans,now);
}
printf("%.2lfn",ans);
}

int main(){
while (scanf("%d",&n)!=EOF){
input();
solve();
}
}

【题目大意】
给出两个矩形，让你求一个点，使之满足在两个矩形里的比例位置是一样的。
【算法分析】
Orz。。。比赛时想爬山。但是弄成直接爬那个重合点，然后以他们比例差作为估价函数。
于是果断写不出，然后挂了。
然后赛后问师傅。。。师傅说直接爬外面的，再算在里面的对应位置就可以了。
当时当场Orz自己的傻×无限次。

然后其中一种正确的做法是：
在外面爬，然后算在里面的对应位置，估价函数就设为这两个对应点的距离。

于是一爬就过。。。Orz。。。
【CODE】
#include #include #include #include #include using namespace std;
const double eps=1e-5;
struct Point{double x,y;}a[5],st,xXL,yXL;
double ratex,ratey;

inline double sqr(double x){return x*x;}
inline double dis(Point A,Point B){return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));}

void input(){
scanf("%lf%lf",&st.x,&st.y);
for (int i=1;i<=4;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
ratex=dis(a[1],a[2])/st.x;
ratey=dis(a[1],a[4])/st.y;

xXL.x=a[2].x-a[1].x;
xXL.y=a[2].y-a[1].y;

yXL.x=a[4].x-a[1].x;
yXL.y=a[4].y-a[1].y;
}

double w(double x,double y){
if (x<0 || x>st.x || y<0 || y>st.y) return 1e50;
double rx=x/st.x,ry=y/st.y;
Point m,tmp;
tmp.x=x; tmp.y=y;

m.x=rx*xXL.x+ry*yXL.x+a[1].x;
m.y=rx*xXL.y+ry*yXL.y+a[1].y;
return dis(m,tmp);
}

void work(){
double step=1.0,x=0,y=0;
bool flag;
for (;step>eps;step/=2){
for (flag=true;flag;){
flag=false;
if (w(x+step,y) if (w(x-step,y) if (w(x,y+step) if (w(x,y-step) }
}
printf("%.2lf %.2lfn",x,y);
}

int main(){
int Tc,i;
scanf("%d",&Tc);
for (i=1;i<=Tc;i++){
input();
work();
}
}