#include #include #include #include #include #include #include // 内部定数 #define D_LINE_MAX 100 // 最大線分数 #define D_VAL_MAX 100 // 最大値 // 内部変数 static FILE *szpFpI; // 入力 static int siLCnt; // 線分数 static double sd1X[D_LINE_MAX * 2]; // 線分の端点X static double sd1Y[D_LINE_MAX * 2]; // 線分の端点Y // 内部変数 - テスト用 #ifdef D_TEST static int siRes; static FILE *szpFpA; static int siTNo; #endif // 出力 int fOut( char *pcpLine // 1行 ) { char lc1Buf[1024]; #ifdef D_TEST fgets(lc1Buf, sizeof(lc1Buf), szpFpA); if (strcmp(lc1Buf, pcpLine)) { siRes = -1; } #else printf("%s", pcpLine); #endif return 0; } // 線分と線分の交差判定 int fIsCrs( double pdSx1 // 線分1始点X , double pdSy1 // 線分1始点Y , double pdEx1 // 線分1終点X , double pdEy1 // 線分1終点Y , double pdSx2 // 線分2始点X , double pdSy2 // 線分2始点Y , double pdEx2 // 線分2終点X , double pdEy2 // 線分2終点Y ) { double ldVal1 = (pdSx2 - pdEx2) * (pdSy1 - pdSy2) + (pdSy2 - pdEy2) * (pdSx2 - pdSx1); double ldVal2 = (pdSx2 - pdEx2) * (pdEy1 - pdSy2) + (pdSy2 - pdEy2) * (pdSx2 - pdEx1); double ldVal3 = (pdSx1 - pdEx1) * (pdSy2 - pdSy1) + (pdSy1 - pdEy1) * (pdSx1 - pdSx2); double ldVal4 = (pdSx1 - pdEx1) * (pdEy2 - pdSy1) + (pdSy1 - pdEy1) * (pdSx1 - pdEx2); return ldVal3 * ldVal4 <= 0 && ldVal1 * ldVal2 <= 0; } // 最大値 - 取得 int fGetMax( int piVal1 // 値1 , int piVal2 // 値2 ) { if (piVal1 > piVal2) { return piVal1; } else { return piVal2; } } // 実行メイン int fMain( ) { int i, j, k; char lc1Buf[1024]; // 線分数 - 取得 fgets(lc1Buf, sizeof(lc1Buf), szpFpI); sscanf(lc1Buf, "%d", &siLCnt); // 線分の端点 - 取得 for (i = 0; i < siLCnt; i++) { fgets(lc1Buf, sizeof(lc1Buf), szpFpI); sscanf(lc1Buf, "%lf%lf%lf%lf", &sd1X[i * 2], &sd1Y[i * 2], &sd1X[i * 2 + 1], &sd1Y[i * 2 + 1]); } // 全直線パターン int liMax = 0; for (i = 0; i < siLCnt * 2; i++) { for (j = i + 1; j < siLCnt * 2; j++) { // 線分拡張 double ldSx, ldSy, ldEx, ldEy; if (sd1X[i] == sd1X[j]) { ldSx = sd1X[i]; ldSy = -D_VAL_MAX; ldEx = sd1X[i]; ldEy = D_VAL_MAX; } else if (sd1Y[i] == sd1Y[j]) { ldSx = -D_VAL_MAX; ldSy = sd1Y[i]; ldEx = D_VAL_MAX; ldEy = sd1Y[i]; } else { double ldR = (sd1Y[i] - sd1Y[j]) / (sd1X[i] - sd1X[j]); ldSx = -D_VAL_MAX; ldSy = ldR * ldSx; ldEx = D_VAL_MAX; ldEy = ldR * ldEx; } // 全線分と交差チェック int liCnt = 0; for (k = 0; k < siLCnt; k++) { liCnt += fIsCrs(ldSx, ldSy, ldEx, ldEy, sd1X[k * 2], sd1Y[k * 2], sd1X[k * 2 + 1], sd1Y[k * 2 + 1]); } // 最大交差数 - 更新 liMax = fGetMax(liMax, liCnt); } } return liMax; } // 1回実行 int fOne( ) { int liRet; char lc1Buf[1024]; // 入力 - セット #ifdef D_TEST sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo); szpFpI = fopen(lc1Buf, "r"); sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo); szpFpA = fopen(lc1Buf, "r"); siRes = 0; #else szpFpI = stdin; #endif // 実行メイン liRet = fMain(); // 出力 sprintf(lc1Buf, "%d\n", liRet); fOut(lc1Buf); // 残データ有無 #ifdef D_TEST lc1Buf[0] = '\0'; fgets(lc1Buf, sizeof(lc1Buf), szpFpA); if (strcmp(lc1Buf, "")) { siRes = -1; } #endif // テストファイルクローズ #ifdef D_TEST fclose(szpFpI); fclose(szpFpA); #endif // テスト結果 #ifdef D_TEST if (siRes == 0) { printf("OK %d\n", siTNo); } else { printf("NG %d\n", siTNo); } #endif return 0; } // プログラム開始 int main() { #ifdef D_TEST int i; for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) { siTNo = i; fOne(); } #else fOne(); #endif return 0; }