| ||||||||||
| 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