Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
100题目纪念#include <stdio.h> #include <string.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <ctype.h> #define MAX_N 13+5 #define MAX_INT 0x3f3f3f3f typedef struct { int x; int y; }Point; typedef struct { Point A; Point B; }Line; typedef struct { int x1; int y1; int x2; int y2; }LineT; //struct LineT { int x1; int y1; int x2; int y2; }; int n = 0; Line stLine[MAX_N]; int iMaxix[MAX_N][MAX_N]; void initVar() { int i, j; memset((char *)&stLine, 0, sizeof(stLine)); for(i = 0; i<n; i++) { for(j = 0; j<n; j++) { if(i == j) iMaxix[i][j] = 0; else iMaxix[i][j] = MAX_INT; } } } void printfMatrix() { int i, j; for(i = 0; i<n; i++) { for(j = 0; j<n; j++) { printf("%12d", iMaxix[i][j]); } printf("\n"); } } int crossProduct(Point P0, Point P1, Point P2) { int iTemp = (P1.x - P0.x)* (P2.y -P0.y) - (P2.x- P0.x) *(P1.y - P0.y); //printf("iTemp is %d\n", iTemp); return iTemp; } int max(int a, int b) { if(a>b) return a; else return b; } int min(int a, int b) { if(a<b) return a; else return b; } int IsLineCross(Line H, Line K) { if( max(H.A.x, H.B.x)< min(K.A.x, K.B.x) || max(H.A.y, H.B.y)< min(K.A.y, K.B.y) || max(K.A.x, K.B.x)< min(H.A.x, H.B.x) || max(K.A.y, K.B.y)< min(H.A.y, H.B.y) ) { // printf("coordinate is out of band\n"); return 0; } if(crossProduct(H.A, K.A, H.B) * crossProduct(H.A, K.B, H.B) >0 || crossProduct(K.A, H.A, K.B) * crossProduct(K.A, H.B, K.B) >0) { // printf("coordinate crossProduct is bigger than zero\n"); return 0; } // printf("coordinate is meet requirement cross\n"); return 1; } void IsTwoLineCross() { int i, j; LineT l1, l2; for(i = 0; i<n; i++) { for(j = i; j<n; j++) { if(i == j) continue; //printf("i = %d, j = %d\n", i, j); l1.x1= stLine[i].A.x; l1.y1= stLine[i].A.y; l1.x2= stLine[i].B.x; l1.y2= stLine[i].B.y; l2.x1= stLine[j].A.x; l2.y1= stLine[j].A.y; l2.x2= stLine[j].B.x; l2.y2= stLine[j].B.y; //intersection(l1, l2); if(1 == IsLineCross(stLine[i],stLine[j]) ) { iMaxix[i][j] = 0; iMaxix[j][i] = 0; } } } } void floyd() { int i, j , k; for(k = 0; k<n; k++) for(i = 0; i<n; i++) { for(j = i; j<n; j++) { if(i == j) continue; if(iMaxix[i][j] == MAX_INT && iMaxix[i][k] == 0 && iMaxix[k][j] == 0) { iMaxix[i][j] = 0; iMaxix[j][i] = 0; } } } } int intersection( LineT l1, LineT l2) { //快速排斥实验 if ((l1.x1 > l1.x2 ? l1.x1 : l1.x2) < (l2.x1 < l2.x2 ? l2.x1 : l2.x2) || (l1.y1 > l1.y2 ? l1.y1 : l1.y2) < (l2.y1 < l2.y2 ? l2.y1 : l2.y2) || (l2.x1 > l2.x2 ? l2.x1 : l2.x2) < (l1.x1 < l1.x2 ? l1.x1 : l1.x2) || (l2.y1 > l2.y2 ? l2.y1 : l2.y2) < (l1.y1 < l1.y2 ? l1.y1 : l1.y2)) { printf("TT coordinate is out of band\n"); return 0; } //跨立实验 if ((((l1.x1 - l2.x1)*(l2.y2 - l2.y1) - (l1.y1 - l2.y1)*(l2.x2 - l2.x1))* ((l1.x2 - l2.x1)*(l2.y2 - l2.y1) - (l1.y2 - l2.y1)*(l2.x2 - l2.x1))) > 0 || (((l2.x1 - l1.x1)*(l1.y2 - l1.y1) - (l2.y1 - l1.y1)*(l1.x2 - l1.x1))* ((l2.x2 - l1.x1)*(l1.y2 - l1.y1) - (l2.y2 - l1.y1)*(l1.x2 - l1.x1))) > 0) { printf("TT coordinate crossProduct is bigger than zero\n"); return 0; } printf("TT coordinate is meet requirement cross\n"); return 1; } int main() { int i, j; int line1, line2 ; while(scanf("%d", &n)) { //printf("n = %d\n", n); if(0 == n) break; initVar(); for(i = 0; i<n; i++) { scanf("%d %d %d %d", &stLine[i].A.x, &stLine[i].A.y, &stLine[i].B.x, &stLine[i].B.y); // printf("i = %d, stLine[i].A.x = %d, stLine[i].A.y = %d, stLine[i].B.x = %d, stLine[i].B.y = %d\n",i, stLine[i].A.x, stLine[i].A.y, stLine[i].B.x, stLine[i].B.y); } //printf("before IsTwoLineCross \n"); //printfMatrix(); IsTwoLineCross(); //printf("after IsTwoLineCross \n"); //printfMatrix(); floyd(); //printf("after floyd \n\n\n"); //printfMatrix(); while(scanf("%d %d", &line1, &line2)) { //printf("line1 is %d, line2 is %d\n", line1, line2); if( 0 == line1 && 0 == line2) break; if(0 == iMaxix[line1-1][line2-1]) printf("CONNECTED\n"); else printf("NOT CONNECTED\n"); } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator