livedoor2008年11月20日
#0012 A Point in a Triangle
平面上に (x1, y1), (x2, y2), (x3, y3) を頂点とした三角形と点 P(xp, yp) があります。点 P が三角形の内部にあるなら YES、三角形の外部にあるなら NO を出力して終了するプログラムを作成して下さい。
なお、与える点 P は三角形の頂点や辺の上にはないものとし、x1, y1, x2, y2, x3, y3 xp, yp は、それぞれ -100 以上 100 以下とします。
Input
複数のデータセットが与えられます。各データセットの形式は以下のようになっています。
x1 y1 x2 y2 x3 y3 xp yp
与えられる入力は全て実数です。入力の最後まで処理して下さい。
Output
書くデータセットに対して、YES または NO を１行に出力して下さい。
Sample Input
0.0 0.0 2.0 0.0 2.0 2.0 1.5 0.5
0.0 0.0 1.0 4.0 5.0 3.0 -1.0 3.0
Output for the Sample Input
YES
NO
-----------------------------------------------------------------
#include
#include
using namespace std;
typedef struct POINT_tag//座標の構造体
{
float x;//x座標
float y;//y座標
}POINT_t;
typedef struct LINE_tag//線分を格納する構造体
{
POINT_t a;//始点
POINT_t b;//終点
}LINE_t;
typedef struct TRIANGLE_tag//三角形として格納する構造体
{
POINT_t a;
POINT_t b;
POINT_t c;
}TRIANGLE_t;
int side(POINT_t *p,LINE_t *e){ //線がどっち側にあるのか判定
float n;
POINT_t p1 = *p; //pのポインタをp1に設定
POINT_t p2 = e->a;//有向線分eの始点
POINT_t p3 = e->b;//有向線分eの終点
n = p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y -p2.y);//有効線分の外積を求める
if(n>0) return 1;//右
else if(n<0)return -1;//左
else return 0;//線上
}
int PointInTriangle(POINT_t *p,TRIANGLE_t *t){//三角形の中に点が入ってるかどうかを確認する
LINE_t ab,bc,ca;
ab.a = t->a;
ab.b = t->b;
bc.a = t->b;
bc.b = t->c;
ca.a = t->c;
ca.b = t ->a;
const int pab = side(p,&ab);//有向線分abから見た点pの方向
const int pbc = side(p,&bc);//有向線分bcから見た点pの方向
const int pca = side(p,&ca);//有向線分caから見た点pの方向
// 三角形の内側にあれば正
if ( (0 < pab) && (0 < pbc) && (0 < pca) )
return 1; // 点 p が常に右手にある（時計回り）
if ( (0 > pab) && (0 > pbc) && (0 > pca) )
return 1; // 点 p が常に左側にある（反時計回り）
else return 0;
}
//たぶん点を増やしたり減らしたりしたらいろいろな図形に代用できる
int main(void){
POINT_t tri1,inp;
//求めたいトライアングル.求める点.x,yどちらの座標か
while(EOF != scanf("%f %f %f %f %f %f %f %f",&tri1.a.x,&tri1.a.y,&tri1.b.x,&tri1.b.y,&tri1.c.x,&tri1.c.y,&inp.x,&inp.y)){
if(1==PointInTriangle(&inp,&tri1)){
printf("YES\n");
}else{
printf("NO\n");
}
}
return 0;
}
-------------------------------------------------------------
なお、与える点 P は三角形の頂点や辺の上にはないものとし、x1, y1, x2, y2, x3, y3 xp, yp は、それぞれ -100 以上 100 以下とします。
Input
複数のデータセットが与えられます。各データセットの形式は以下のようになっています。
x1 y1 x2 y2 x3 y3 xp yp
与えられる入力は全て実数です。入力の最後まで処理して下さい。
Output
書くデータセットに対して、YES または NO を１行に出力して下さい。
Sample Input
0.0 0.0 2.0 0.0 2.0 2.0 1.5 0.5
0.0 0.0 1.0 4.0 5.0 3.0 -1.0 3.0
Output for the Sample Input
YES
NO
-----------------------------------------------------------------
#include
#include
using namespace std;
typedef struct POINT_tag//座標の構造体
{
float x;//x座標
float y;//y座標
}POINT_t;
typedef struct LINE_tag//線分を格納する構造体
{
POINT_t a;//始点
POINT_t b;//終点
}LINE_t;
typedef struct TRIANGLE_tag//三角形として格納する構造体
{
POINT_t a;
POINT_t b;
POINT_t c;
}TRIANGLE_t;
int side(POINT_t *p,LINE_t *e){ //線がどっち側にあるのか判定
float n;
POINT_t p1 = *p; //pのポインタをp1に設定
POINT_t p2 = e->a;//有向線分eの始点
POINT_t p3 = e->b;//有向線分eの終点
n = p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y -p2.y);//有効線分の外積を求める
if(n>0) return 1;//右
else if(n<0)return -1;//左
else return 0;//線上
}
int PointInTriangle(POINT_t *p,TRIANGLE_t *t){//三角形の中に点が入ってるかどうかを確認する
LINE_t ab,bc,ca;
ab.a = t->a;
ab.b = t->b;
bc.a = t->b;
bc.b = t->c;
ca.a = t->c;
ca.b = t ->a;
const int pab = side(p,&ab);//有向線分abから見た点pの方向
const int pbc = side(p,&bc);//有向線分bcから見た点pの方向
const int pca = side(p,&ca);//有向線分caから見た点pの方向
// 三角形の内側にあれば正
if ( (0 < pab) && (0 < pbc) && (0 < pca) )
return 1; // 点 p が常に右手にある（時計回り）
if ( (0 > pab) && (0 > pbc) && (0 > pca) )
return 1; // 点 p が常に左側にある（反時計回り）
else return 0;
}
//たぶん点を増やしたり減らしたりしたらいろいろな図形に代用できる
int main(void){
POINT_t tri1,inp;
//求めたいトライアングル.求める点.x,yどちらの座標か
while(EOF != scanf("%f %f %f %f %f %f %f %f",&tri1.a.x,&tri1.a.y,&tri1.b.x,&tri1.b.y,&tri1.c.x,&tri1.c.y,&inp.x,&inp.y)){
if(1==PointInTriangle(&inp,&tri1)){
printf("YES\n");
}else{
printf("NO\n");
}
}
return 0;
}
-------------------------------------------------------------
2008年10月31日
#0014 Integral
Integral
+問題---------------------------------------------------------
という３つの線で囲まれる部分の面積を求める方法について考えます。高校で学習する積分を利用するとその面積は 72000000 であるとわかりますが、下図のような多数の長方形の面積の和を求めることによって、それに極めて近い値を得ることができます。
長方形の横の長さを d とおくと、ｓの近似的な値は
縦の長さが f( d ) で横の長さが d である長方形の面積
+ 縦の長さが f( 2d ) で横の長さが d である長方形の面積
+ 縦の長さが f( 3d ) で横の長さが d である長方形の面積
...
+ 縦の長さが f( 600 - d ) で横の長さが d である長方形の面積
です。d を小さくすればするほど、この値は 72000000 に近づきます。600 の約数 d を入力として受け取り、上記の方式で求めた近似的な面積を出力して終了するプログラムを作成して下さい。
+Input-----------------------------------------------------------
複数のデータセットが与えられます。各データセットには整数 d が一行に与えられます。入力の最後まで処理して下さい。
+Output-----------------------------------------------------------
各データセットに対して、近似的な面積 （整数）を１行に出力して下さい。
+Sample Input-----------------------------------------------------
20
10
+Output for the Sample Input--------------------------------------
68440000
70210000
----------------------------------------------------------------
高校の情報処理検定とかに出てきそうな問題でした。
ひたすら四角形の面積を合計していきます。
読解力が無くてtate変数を2回掛ける必要があるのに気づいたのは
内緒のお話。
-----------------------------------------------------------------
#include < stdio.h >
int main(void){
long tate,inp,sum=0,count=0;
while(EOF != scanf("%ld",&inp)){
tate=600;
sum=0;
while(tate>0){
printf("%d\n",tate);
tate-=inp;
sum+=inp*tate*tate;
}
printf("%ld\n",sum);
}
return 0;
}
+問題---------------------------------------------------------
という３つの線で囲まれる部分の面積を求める方法について考えます。高校で学習する積分を利用するとその面積は 72000000 であるとわかりますが、下図のような多数の長方形の面積の和を求めることによって、それに極めて近い値を得ることができます。
長方形の横の長さを d とおくと、ｓの近似的な値は
縦の長さが f( d ) で横の長さが d である長方形の面積
+ 縦の長さが f( 2d ) で横の長さが d である長方形の面積
+ 縦の長さが f( 3d ) で横の長さが d である長方形の面積
...
+ 縦の長さが f( 600 - d ) で横の長さが d である長方形の面積
です。d を小さくすればするほど、この値は 72000000 に近づきます。600 の約数 d を入力として受け取り、上記の方式で求めた近似的な面積を出力して終了するプログラムを作成して下さい。
+Input-----------------------------------------------------------
複数のデータセットが与えられます。各データセットには整数 d が一行に与えられます。入力の最後まで処理して下さい。
+Output-----------------------------------------------------------
各データセットに対して、近似的な面積 （整数）を１行に出力して下さい。
+Sample Input-----------------------------------------------------
20
10
+Output for the Sample Input--------------------------------------
68440000
70210000
----------------------------------------------------------------
高校の情報処理検定とかに出てきそうな問題でした。
ひたすら四角形の面積を合計していきます。
読解力が無くてtate変数を2回掛ける必要があるのに気づいたのは
内緒のお話。
-----------------------------------------------------------------
#include < stdio.h >
int main(void){
long tate,inp,sum=0,count=0;
while(EOF != scanf("%ld",&inp)){
tate=600;
sum=0;
while(tate>0){
printf("%d\n",tate);
tate-=inp;
sum+=inp*tate*tate;
}
printf("%ld\n",sum);
}
return 0;
}
#0008 Sum of 4 Integers
Sum of 4 Integers
＋問題--------------------------------------------------
50 以下の正の整数 n を入力し、0 〜 9 の範囲の整数 a, b, c, d の組で
a + b + c + d = n
を満たすものの組み合わせ数を出力するプログラムを作成して下さい。
例えば、n が 35 のとき、(a, b, c, d) は (8,9,9,9)、(9,8,9,9)、(9,9,8,9)、(9,9,9,8) の 4 通りですので、答えは 4 となります。
＋Input−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
複数のデータセットが与えられます。各データセットに n が１行に与えられます。入力の最後まで処理して下さい。
+Output----------------------------------------------------------
各データセットごとに、a, b, c, d の組み合わせ個数を１行に出力して下さい。
+Sample Input-----------------------------------------------------
35
1
+Output for the Sample Input--------------------------------------
4
4
-----------------------------------------------------------------
なんとか、無事解けてくれました。
効率は悪いでしょうが、計算量はそこまで多くないので総当たり大作戦で。
インプットごとに0000〜9999までを調べて比較します。
36以上は無理なので無視で。
----------------------------------------------------
#include <stdio.h>
int main(void){
int a,i1,i2,i3,i4,ans;
while(EOF != scanf("%d",&a)){
ans=0;
if(a>36){ //9*4=36 これ以上の値はありえないので出たら全部０
ans=0;
}else{
for(i4=9;i4>=0;i4--){
for(i3=9;i3>=0;i3--){
for(i2=9;i2>=0;i2--){
for(i1=9;i1>=0;i1--){
if((i1+i2+i3+i4)==a)ans++;//総当たりで検索してaと同じになったらansに1を足す。
}
}
}
}
}
printf("%d\n",ans);//ansを出力
}
return 0;
}
＋問題--------------------------------------------------
50 以下の正の整数 n を入力し、0 〜 9 の範囲の整数 a, b, c, d の組で
a + b + c + d = n
を満たすものの組み合わせ数を出力するプログラムを作成して下さい。
例えば、n が 35 のとき、(a, b, c, d) は (8,9,9,9)、(9,8,9,9)、(9,9,8,9)、(9,9,9,8) の 4 通りですので、答えは 4 となります。
＋Input−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
複数のデータセットが与えられます。各データセットに n が１行に与えられます。入力の最後まで処理して下さい。
+Output----------------------------------------------------------
各データセットごとに、a, b, c, d の組み合わせ個数を１行に出力して下さい。
+Sample Input-----------------------------------------------------
35
1
+Output for the Sample Input--------------------------------------
4
4
-----------------------------------------------------------------
なんとか、無事解けてくれました。
効率は悪いでしょうが、計算量はそこまで多くないので総当たり大作戦で。
インプットごとに0000〜9999までを調べて比較します。
36以上は無理なので無視で。
----------------------------------------------------
#include <stdio.h>
int main(void){
int a,i1,i2,i3,i4,ans;
while(EOF != scanf("%d",&a)){
ans=0;
if(a>36){ //9*4=36 これ以上の値はありえないので出たら全部０
ans=0;
}else{
for(i4=9;i4>=0;i4--){
for(i3=9;i3>=0;i3--){
for(i2=9;i2>=0;i2--){
for(i1=9;i1>=0;i1--){
if((i1+i2+i3+i4)==a)ans++;//総当たりで検索してaと同じになったらansに1を足す。
}
}
}
}
}
printf("%d\n",ans);//ansを出力
}
return 0;
}
#004 Simultaneous Equation
連立方程式を解こう。という問題です。
うむむ。サンプルインプットは通るのですが、
なかなかうまいこと通ってくれません。
----------------------------------------------------
連立方程式
ax + by = c
bx + ey = f
の解、x, y を出力して終了するプログラムを作成して下さい。a, b, c, d, e, f はそれぞれ、 -1000 以上 1000 以下の実数とし、連立方程式の解が一意に存在するように与えれれるものとします。
----------------------------------------------------------
Input
複数のデータセットが与えられます。入力の最後まで処理して下さい。１つのデータセットが１行に与えられます。１つのデータセットに a, b, c, d, e, f が１つのスペースで区切られて与えられます。
-----------------------------------------------------------
Output
各データセットに対して、x, y を１つのスペースで区切って１行に出力して下さい。各値は小数点以下第３位まで出力して下さい。小数点以下第４位を四捨五入して下さい。
-------------------------------------------------------------
Sample Input
1 2 3 4 5 6
2 -1 -2 -1 -1 -5
Output for the Sample Input
-1.000 2.000
1.000 4.000
---------------------------------------------------------------
で、組んでみたのがこれ。
サンプルは通るということは小数点の計算がうまくできていないんでしょうかねー。
後日、組み直して見ようと思います。
---------------------------------------------------------------
#include <stdio.h>
int main(void){
int i;
double a[3],b[3],s[3],ans[3],cb[3],ca[3];
while(EOF != scanf("%lf %lf %lf %lf %lf %lf",&a[0],&a[1],&a[2],&b[0],&b[1],&b[2])){
for(i=0;i < 3 ; i++)cb[i]=b[i]*a[0];
for(i=0;i < 3 ; i++)ca[i]=b[0]*a[i];
for(i=0;i < 3 ; i++)s[i]=ca[i]-cb[i];
ans[0]= s[2]/s[1];
ans[1]= (b[2]-(b[1]*ans[0]))/b[0];
for(i=0;i<3;i++){
if(ans[i]<0)ans[i]=(int)(ans[i]*1000-0.5);
else ans[i]=(int)(ans[i]*1000+0.5);
}
printf("%.3lf %.3lf\n",ans[1]/1000,ans[0]/1000);
}
return 0;
}
うむむ。サンプルインプットは通るのですが、
なかなかうまいこと通ってくれません。
----------------------------------------------------
連立方程式
ax + by = c
bx + ey = f
の解、x, y を出力して終了するプログラムを作成して下さい。a, b, c, d, e, f はそれぞれ、 -1000 以上 1000 以下の実数とし、連立方程式の解が一意に存在するように与えれれるものとします。
----------------------------------------------------------
Input
複数のデータセットが与えられます。入力の最後まで処理して下さい。１つのデータセットが１行に与えられます。１つのデータセットに a, b, c, d, e, f が１つのスペースで区切られて与えられます。
-----------------------------------------------------------
Output
各データセットに対して、x, y を１つのスペースで区切って１行に出力して下さい。各値は小数点以下第３位まで出力して下さい。小数点以下第４位を四捨五入して下さい。
-------------------------------------------------------------
Sample Input
1 2 3 4 5 6
2 -1 -2 -1 -1 -5
Output for the Sample Input
-1.000 2.000
1.000 4.000
---------------------------------------------------------------
で、組んでみたのがこれ。
サンプルは通るということは小数点の計算がうまくできていないんでしょうかねー。
後日、組み直して見ようと思います。
---------------------------------------------------------------
#include <stdio.h>
int main(void){
int i;
double a[3],b[3],s[3],ans[3],cb[3],ca[3];
while(EOF != scanf("%lf %lf %lf %lf %lf %lf",&a[0],&a[1],&a[2],&b[0],&b[1],&b[2])){
for(i=0;i < 3 ; i++)cb[i]=b[i]*a[0];
for(i=0;i < 3 ; i++)ca[i]=b[0]*a[i];
for(i=0;i < 3 ; i++)s[i]=ca[i]-cb[i];
ans[0]= s[2]/s[1];
ans[1]= (b[2]-(b[1]*ans[0]))/b[0];
for(i=0;i<3;i++){
if(ans[i]<0)ans[i]=(int)(ans[i]*1000-0.5);
else ans[i]=(int)(ans[i]*1000+0.5);
}
printf("%.3lf %.3lf\n",ans[1]/1000,ans[0]/1000);
}
return 0;
}
