ACM ICPC Philippines 2007
First Philippine National Inter-Collegiate Programming Competition
20 October 2007, De La Salle Canlubang
Organized by the Computing Society of the Philippines (CSP)
in cooperation with Association for Computing Machinery (ACM)
Problem C: “NBN”
(Input File: pc.in)
In the City of Nubia, a broadband network needs to be set up to connect the entire city. Connections are from point to point connecting various city agencies. To link the connections with each other, connections are built to intersect with one another forming a junction point. Each connection can have more than one junction point to ensure connectivity and reliability.
Figure 1 shows a possible Nubia broadband network connecting all the city agencies. For simplicity, we assume that all connections are straight lines, and no agencies are left out.
Figure 1: Map of six city agencies and its connection
With numerous scandals that had rocked the City of Nubia, teams of concerned students are determined to develop an algorithm to detect connections that has no junction. Connections with no junction(s) are just redundant connections in the network such as connection CE. This is a way to pad the cost of the network especially if the connections will not be actually built. Thus the developed algorithm must be able to detect that no junction exists. It is also noted that a single-line connection is also not allowed as it has no fail safe feature.
Input:
The input will contain several test cases. The first line will indicate the number of test cases. Each test case begins with a number representing the number of connections between city agencies. The subsequent lines contain the name of the connection followed by four integers, representing the end points of the connection in x, y format. Connections names are represented using two-letters in the English alphabet, where each letter represents a city agency. It is noted that the maximum number of agency is 26. We assume that the top left corner of the map extent is the origin and anything to the left and bottom are the positive axis. It is noted that the coordinate values will be any number from 0 to 999.
Output:
The output shows the connection followed by a remark indicating with intersection or no intersection.
SAMPLE INPUT
2
2
AB, 20, 5, 10, 20
CD, 20, 10, 20, 120
4
AF, 20, 10, 30, 30
BC, 30, 10, 10, 20
CE, 10, 20, 20, 30
DE, 40, 20, 20, 30
OUTPUT FOR THE SAMPLE INPUT:
Case 1:
AB has no junction
CD has no junction
Case 2:
AF has junction
BC has junction
CE has no junction
DE has junction
First Philippine National Inter-Collegiate Programming Competition
20 October 2007, De La Salle Canlubang
Organized by the Computing Society of the Philippines (CSP)
in cooperation with Association for Computing Machinery (ACM)
Problem C: “NBN”
(Input File: pc.in)
In the City of Nubia, a broadband network needs to be set up to connect the entire city. Connections are from point to point connecting various city agencies. To link the connections with each other, connections are built to intersect with one another forming a junction point. Each connection can have more than one junction point to ensure connectivity and reliability.
Figure 1 shows a possible Nubia broadband network connecting all the city agencies. For simplicity, we assume that all connections are straight lines, and no agencies are left out.
Figure 1: Map of six city agencies and its connection
With numerous scandals that had rocked the City of Nubia, teams of concerned students are determined to develop an algorithm to detect connections that has no junction. Connections with no junction(s) are just redundant connections in the network such as connection CE. This is a way to pad the cost of the network especially if the connections will not be actually built. Thus the developed algorithm must be able to detect that no junction exists. It is also noted that a single-line connection is also not allowed as it has no fail safe feature.
Input:
The input will contain several test cases. The first line will indicate the number of test cases. Each test case begins with a number representing the number of connections between city agencies. The subsequent lines contain the name of the connection followed by four integers, representing the end points of the connection in x, y format. Connections names are represented using two-letters in the English alphabet, where each letter represents a city agency. It is noted that the maximum number of agency is 26. We assume that the top left corner of the map extent is the origin and anything to the left and bottom are the positive axis. It is noted that the coordinate values will be any number from 0 to 999.
Output:
The output shows the connection followed by a remark indicating with intersection or no intersection.
SAMPLE INPUT
2
2
AB, 20, 5, 10, 20
CD, 20, 10, 20, 120
4
AF, 20, 10, 30, 30
BC, 30, 10, 10, 20
CE, 10, 20, 20, 30
DE, 40, 20, 20, 30
OUTPUT FOR THE SAMPLE INPUT:
Case 1:
AB has no junction
CD has no junction
Case 2:
AF has junction
BC has junction
CE has no junction
DE has junction
Posts
No comments:
Post a Comment