「AOJProblem Set from CGL 問0～4」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
*Points/Vectors - Projection
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_A
正射影を求める問題。
指定されている有効桁数が大きいことだけに注意。
あとはベクトルの知識からすぐに式がたちます。
#include<stdio.h>
#include<math.h>
int main(){
double x0,y0,x1,y1,x2,y2;
double dx1,dy1,dx2,dy2,lenP1;
scanf("%lf %lf %lf %lf",&x0,&y0,&x1,&y1);
dx1=x1-x0;
dy1=y1-y0;
lenP1=hypot(dx1,dy1);
int q;
scanf("%d",&q);
while(q--){
scanf("%lf %lf",&x2,&y2);
dx2=x2-x0;
dy2=y2-y0;
double T=(dx1*dx2+dy1*dy2)/(lenP1*lenP1);
printf("%.10lf %.10lf\n",x0+dx1*T,y0+dy1*T);
}
}
*Points/Vectors - Reflection
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_B
線対称な点を求める問題。
正射影で求めた点の点対称な位置ですので前の問題のコードを流用します。
#include<stdio.h>
#include<math.h>
int main(){
double x0,y0,x1,y1,x2,y2;
double dx1,dy1,dx2,dy2,lenP1;
scanf("%lf %lf %lf %lf",&x0,&y0,&x1,&y1);
dx1=x1-x0;
dy1=y1-y0;
lenP1=hypot(dx1,dy1);
int q;
scanf("%d",&q);
while(q--){
scanf("%lf %lf",&x2,&y2);
dx2=x2-x0;
dy2=y2-y0;
double T=(dx1*dx2+dy1*dy2)/(lenP1*lenP1);
double tx=x0+T*dx1;
double ty=y0+T*dy1;
printf("%.10lf %.10lf\n",tx*2-x2,ty*2-y2);
}
}
*Points/Vectors - Counter-Clockwise
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_C
ベクトルAからみてベクトルBが時計回りか反時計回りかもしくは同一直線状にあるなら細かく判断する問題。
#include<stdio.h>
#include<math.h>
int main(){
double x0,y0,x1,y1,x2,y2;
double dx1,dy1,dx2,dy2,len1,len2;
scanf("%lf %lf %lf %lf",&x0,&y0,&x1,&y1);
dx1=x1-x0;
dy1=y1-y0;
len1=hypot(dx1,dy1);
int q;
scanf("%d",&q);
while(q--){
scanf("%lf %lf",&x2,&y2);
dx2=x2-x0;
dy2=y2-y0;
double R=dx1*dy2-dx2*dy1;
len2=hypot(dx2,dy2);
if(R>0){
printf("COUNTER_CLOCKWISE\n");
}else if(R<0){
printf("CLOCKWISE\n");
}else{
if(dx1*dx2+dy1*dy2<0){
printf("ONLINE_BACK\n");
}else{
if(len1<len2){
printf("ONLINE_FRONT\n");
}else{
printf("ON_SEGMENT\n");
}
}
}
}
}
*Segments/Lines - Parallel/Orthogonal
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_A
内積が0になれば直交。
外積が0になれば平行。
どちらでもなければ0.
#include<stdio.h>
#include<math.h>
int main(){
double x0,y0,x1,y1,x2,y2,x3,y3;
double dx1,dx3,dy1,dy3;
int q;
scanf("%d",&q);
while(q--){
scanf("%lf %lf %lf %lf",&x0,&y0,&x1,&y1);
scanf("%lf %lf %lf %lf",&x2,&y2,&x3,&y3);
dx1=x1-x0;
dy1=y1-y0;
dx3=x3-x2;
dy3=y3-y2;
double R1=(dx1*dy3-dx3*dy1);
double R2=(dx1*dx3+dy1*dy3);
if(R1==0){
printf("2");
}else if(R2==0){
printf("1");
}else{
printf("0");
}
printf("\n");
}
}
*Points/Vectors - Projection
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_A
正射影を求める問題。
指定されている有効桁数が大きいことだけに注意。
あとはベクトルの知識からすぐに式がたちます。
#include<stdio.h>
#include<math.h>
int main(){
double x0,y0,x1,y1,x2,y2;
double dx1,dy1,dx2,dy2,lenP1;
scanf("%lf %lf %lf %lf",&x0,&y0,&x1,&y1);
dx1=x1-x0;
dy1=y1-y0;
lenP1=hypot(dx1,dy1);
int q;
scanf("%d",&q);
while(q--){
scanf("%lf %lf",&x2,&y2);
dx2=x2-x0;
dy2=y2-y0;
double T=(dx1*dx2+dy1*dy2)/(lenP1*lenP1);
printf("%.10lf %.10lf\n",x0+dx1*T,y0+dy1*T);
}
}
*Points/Vectors - Reflection
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_B
線対称な点を求める問題。
正射影で求めた点の点対称な位置ですので前の問題のコードを流用します。
#include<stdio.h>
#include<math.h>
int main(){
double x0,y0,x1,y1,x2,y2;
double dx1,dy1,dx2,dy2,lenP1;
scanf("%lf %lf %lf %lf",&x0,&y0,&x1,&y1);
dx1=x1-x0;
dy1=y1-y0;
lenP1=hypot(dx1,dy1);
int q;
scanf("%d",&q);
while(q--){
scanf("%lf %lf",&x2,&y2);
dx2=x2-x0;
dy2=y2-y0;
double T=(dx1*dx2+dy1*dy2)/(lenP1*lenP1);
double tx=x0+T*dx1;
double ty=y0+T*dy1;
printf("%.10lf %.10lf\n",tx*2-x2,ty*2-y2);
}
}
*Points/Vectors - Counter-Clockwise
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_C
ベクトルAからみてベクトルBが時計回りか反時計回りかもしくは同一直線状にあるなら細かく判断する問題。
#include<stdio.h>
#include<math.h>
int main(){
double x0,y0,x1,y1,x2,y2;
double dx1,dy1,dx2,dy2,len1,len2;
scanf("%lf %lf %lf %lf",&x0,&y0,&x1,&y1);
dx1=x1-x0;
dy1=y1-y0;
len1=hypot(dx1,dy1);
int q;
scanf("%d",&q);
while(q--){
scanf("%lf %lf",&x2,&y2);
dx2=x2-x0;
dy2=y2-y0;
double R=dx1*dy2-dx2*dy1;
len2=hypot(dx2,dy2);
if(R>0){
printf("COUNTER_CLOCKWISE\n");
}else if(R<0){
printf("CLOCKWISE\n");
}else{
if(dx1*dx2+dy1*dy2<0){
printf("ONLINE_BACK\n");
}else{
if(len1<len2){
printf("ONLINE_FRONT\n");
}else{
printf("ON_SEGMENT\n");
}
}
}
}
}
*Segments/Lines - Parallel/Orthogonal
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_A
内積が0になれば直交。
外積が0になれば平行。
どちらでもなければ0.
#include<stdio.h>
#include<math.h>
int main(){
double x0,y0,x1,y1,x2,y2,x3,y3;
double dx1,dx3,dy1,dy3;
int q;
scanf("%d",&q);
while(q--){
scanf("%lf %lf %lf %lf",&x0,&y0,&x1,&y1);
scanf("%lf %lf %lf %lf",&x2,&y2,&x3,&y3);
dx1=x1-x0;
dy1=y1-y0;
dx3=x3-x2;
dy3=y3-y2;
double R1=(dx1*dy3-dx3*dy1);
double R2=(dx1*dx3+dy1*dy3);
if(R1==0){
printf("2");
}else if(R2==0){
printf("1");
}else{
printf("0");
}
printf("\n");
}
}
*Segments/Lines - Intersection
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_B
同一直線上に２本の線がある場合の判定で結構困った問題。
採点データを作った人の掌の上で踊ってしまった感じがする。
勉強になりました。
#include<stdio.h>
#include<math.h>
bool isFlat(double x0,double y0,double x1,double y1,double x2,double y2,double x3,double y3){
double dx1,dy1,dx2,dy2,dx3,dy3,R1,R2;
dx1=x1-x0;
dy1=y1-y0;
dx2=x2-x0;
dy2=y2-y0;
dx3=x3-x0;
dy3=y3-y0;
R1=dx1*dx2+dy1*dy2;
R2=dx1*dx3+dy1*dy3;
if(R1<=0&&0<=R2)return true;
if(R2<=0&&0<=R1)return true;
return false;
}
bool isCrossHerf(double x0,double y0,double x1,double y1,double x2,double y2,double x3,double y3){
double dx1,dy1,dx2,dy2,dx3,dy3;
dx1=x1-x0;
dy1=y1-y0;
dx2=x2-x0;
dy2=y2-y0;
dx3=x3-x0;
dy3=y3-y0;
double R1=dx1*dy2-dx2*dy1;
double R2=dx1*dy3-dx3*dy1;
if(0<R1&&R2<=0)return true;
if(0<=R1&&R2<0)return true;
if(0<R2&&R1<=0)return true;
if(0<=R2&&R1<0)return true;
if(R1==0&&R2==0){
bool Hit1=isFlat(x0,y0,x1,y1,x2,y2,x3,y3);
bool Hit2=isFlat(x1,y1,x0,y0,x2,y2,x3,y3);
bool Hit3=isFlat(x2,y2,x3,y3,x0,y0,x1,y1);
bool Hit4=isFlat(x3,y3,x2,y2,x0,y0,x1,y1);
return Hit1||Hit2||Hit3||Hit4;
}
return false;
}
int main(){
double x0,y0,x1,y1,x2,y2,x3,y3;
double dx1,dx3,dy1,dy3;
int q;
scanf("%d",&q);
while(q--){
scanf("%lf %lf %lf %lf",&x0,&y0,&x1,&y1);
scanf("%lf %lf %lf %lf",&x2,&y2,&x3,&y3);
bool ok=isCrossHerf(x0,y0,x1,y1,x2,y2,x3,y3)&&isCrossHerf(x2,y2,x3,y3,x0,y0,x1,y1);
printf("%d\n",ok?1:0);
}
}
