Jun 24 2014

UVa 349 - Transferable Voting (II)

Problem

The Transferable Vote system for determining the winner of an election requires that a successful candidate obtain an absolute majority of the votes cast, even when there are more than two candidates. To achieve this goal, each voter completes his or her ballot by listing all the candidates in order of preference. Thus if there are five candidates for a single position, each voter’s ballot must contain five choices, from first choice to fifth choice.

In this problem you are to determine the winner, if any, of elections using the Transferable Vote system. If there are c candidates for the single position, then each voter’s ballot will include c distinct choices, corresponding to identifying the voter’s first place, second place, tex2html_wrap_inline32 , and nth place selections. Invalid ballots will be discarded, but their presence will be noted. A ballot is invalid if a voter’s choices are not distinct (choosing the same candidate as first and second choice isn’t permitted) or if any of the choices aren’t legal (that is, in the range 1 to c).

For each election candidates will be assigned sequential numbers starting with 1. The maximum number of voters in this problem will be 100, and the maximum number of candidates will be 5.

                           Table A                 Table B
               -------------------------------    --------- 
               Voter    First   Second  Third
                        Choice  Choice  Choice
                 1        1       2       4
                 2        1       3       2       1   3   2
                 3        3       2       1       3   2   1
                 4        3       2       1       3   2   1
                 5        1       2       3       1   2   3
                 6        2       3       1       3   1
                 7        3       2       1       3   2   1
                 8        3       1       1
                 9        3       2       1       3   2   1
                10        1       2       3       1   2   3
                11        1       3       2       1   3   2
                12        2       3       1       3   1

Consider a very small election. In Table A are the votes from the 12 voters for the three candidates. Voters 1 and 8 cast invalid ballots; they will not be counted. This leaves 10 valid ballots, so a winning candidate will require at least 6 votes (the least integer value greater than half the number of valid ballots) to win. Candidates 1 and 3 each have 4 first choice votes, and candidate 2 has two. There is no majority, so the candidate with the fewest first choice votes, candidate 2, is eliminated. If there had been several candidates with the fewest first choice votes, any of them, selected at random, could be selected for elimination.

With candidate 2 eliminated, we advance the second and third choice candidates from those voters who voted for candidate 2 as their first choice. The result of this action is shown in Table B. Now candidate 3 has picked up 2 additional votes, giving a total of 6. This is sufficient for election. Note that if voter 12 had cast the ballot 2 1 3 then there would have been a tie between candidates 1 and 3.

Input

There will be one or more elections to consider. Each will begin with a line containing the number of candidates and the number of voters, c and n. Data for the last election will be followed by a line containing two zeroes.

Following the first line for each election will be n additional lines each containing the choices from a single ballot. Each line will contain only c non-negative integers separated by whitespace.

Output

For each election, print a line identifying the election number (they are numbered sequentially starting with 1). If there were any invalid ballots, print an additional line specifying the number of such. Finally, print a line indicating the winner of the election, if any, or indication of a tie; be certain to identify the candidates who are tied. Look at the samples below for the exact output format.

Sample Input

Sample Output

Election #1
   2 bad ballot(s)
   Candidate 3 is elected.
Election #2
   2 bad ballot(s)
   The following candidates are tied: 1 3
Election #3
   1 bad ballot(s)
   Candidate 3 is elected.

Solution

題目描述：

投票時紀錄自願序，接著每一輪刷掉得票數量最小的候選人，直到所有候選人得票數皆相同或者只剩下一個候選人。若自願序中前位者遭到刷掉，則由下一個志願候選人替補。

如果發現志願序中有重複候選人、或者是不存在的候選人則將此票視為廢票。

題目解法：

模擬！

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
	int n, m, cases = 0, x;
	while(scanf("%d %d", &n, &m) == 2 && n+m) {
		int bad[1024] = {}, A[1024][16];
		int badCount = 0;
		for(int i = 0; i < m; i++) {
			int mark[16] = {};
			for(int j = 0; j < n; j++) {
				scanf("%d", &x);
				A[i][j] = x;
				if(x > n || x < 1) {
					bad[i] = 1;
					continue;
				}
				mark[x]++;
				if(mark[x] > 1)
					bad[i] = 1;
			}
			badCount += bad[i];
		}
		
		printf("Election #%d\n", ++cases);
		printf("   %d bad ballot(s)\n", badCount);
		
		int Atop[1024] = {}, alive[1024] = {}, aliveCount = n;
		for(int i = 1; i < n; i++) {
			int votes[16] = {}, mx = 0, del = -1;
			for(int j = 0; j < m; j++) {
				if(bad[j])	continue;
				while(alive[A[j][Atop[j]]])
					Atop[j]++;
				votes[A[j][Atop[j]]]++;
			}
			for(int j = 1; j <= n; j++)
				mx = max(mx, votes[j]);
			for(int j = 1; j <= n; j++) {
				if(votes[j] < mx && alive[j] == 0)
					del = j, mx = votes[j];
			}
			if(del == -1)	break;
			alive[del] = 1, aliveCount--;
		}
		if(aliveCount == 1) {
			for(int i = 1; i <= n; i++)
				if(alive[i] == 0)
					printf("   Candidate %d is elected.\n", i);
		} else {
			printf("   The following candidates are tied:");
			for(int i = 1; i <= n; i++)
				if(alive[i] == 0)
					printf(" %d", i);
			puts("");
		}
	}
	return 0;
}

Read More +

Jun 24 2014

解題區►解題區 - UVa

UVa 302 - John's trip

Problem

Little Johnny has got a new car. He decided to drive around the town to visit his friends. Johnny wanted to visit all his friends, but there was many of them. In each street he had one friend. He started thinking how to make his trip as short as possible. Very soon he realized that the best way to do it was to travel through each street of town only once. Naturally, he wanted to finish his trip at the same place he started, at his parents’ house.

The streets in Johnny’s town were named by integer numbers from 1 to n, n < 1995. The junctions were independently named by integer numbers from 1 to m, tex2html_wrap_inline32 . All junctions in the town had different numbers. Each street was connecting exactly two (not necessarily different) junctions. No two streets in the town had the same number. He immediately started to plan his round trip. If there was more than one such round trip, he would have chosen the one which, when written down as a sequence of street numbers is lexicographically the smallest.

But Johnny was not able to find even one such round trip. Help Johnny and write a program which finds the desired shortest round trip. If the round trip does not exist the program should write a message. Assume that Johnny lives at the junction ending the 1st street input with smaller number. All streets in the town are two way. There exists a way from each street to another street in the town. The streets in the town are very narrow and there is no possibility to turn back the car once he is in the street.

Input

Input file consists of several blocks. Each block describes one town. Each line in the block contains three integers x, y, z, where x > 0 and y > 0 are the numbers of junctions which are connected by the street number z. The end of the block is marked by the line containing x = y = 0. At the end of the input file there is an empty block, x = y = 0.

Output

The output file consists of 2 line blocks corresponding to the blocks of the input file. The first line of each block contains the sequence of street numbers (single members of the sequence are separated by space) describing Johnny’s round trip. If the round trip cannot be found the corresponding output block contains the message ``Round trip does not exist.’’. The second line of each block is empty.

Sample Input

Sample Output

1
2
3

1 2 3 5 4 6
Round trip does not exist.

Solution

題目描述：

每一條路上都有編號，並且每個編號唯一且個數小於 44。

求一條經過所有邊且不重複的環道。

題目解法：

記得注意起始是第一條邊最小編號的點。

之後對於每一個點相鄰邊根據編號進行排序即可，按著窮舉思路由小開始枚舉即可。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;
struct edge {
	int to, label;
	edge(int a=0, int b=0):
		to(a), label(b) {}
	bool operator<(const edge &x) const {
		return label < x.label;
	}
};
#define MAXN 2048
vector<edge> g[MAXN];
int label_used[MAXN];
deque<int>	path;
void dfs(int u) {
    for(int i = 0; i < g[u].size(); i++) {
        if(label_used[g[u][i].label] == 0) {
        	label_used[g[u][i].label] = 1;
            dfs(g[u][i].to);
            path.push_front(g[u][i].label);
        }
    }
}
int main() {
	int x, y, z;
    while(true) {
    	for(int i = 0; i < MAXN; i++)
    		g[i].clear();
    	int e = 0, start = 0;
    	while(scanf("%d %d", &x, &y) == 2) {
    		if(x == 0 && y == 0)
    			break;
    		/* Johnny lives at the junction ending the 1st street 
				input with smaller number. */
    		if(e == 0)
    			start = min(x, y);
    		scanf("%d", &z);
    		g[x].push_back(edge(y, z));
    		g[y].push_back(edge(x, z));
    		e++;
    	}
    	if(e == 0)	break;
    	
    	int odd = 1;
    	for(int i = 0; i < MAXN; i++) {
    		odd &= g[i].size()%2 == 0;
    	}
    	if(!odd) {
    		puts("Round trip does not exist.\n");
    		continue;
    	}
    	for(int i = 0; i < MAXN; i++)
    		sort(g[i].begin(), g[i].end());
    	memset(label_used, 0, sizeof(label_used));
    	path.clear();
    	dfs(start);
    	for(int i = 0; i < path.size(); i++) 
    		printf("%d%c", path[i], i == path.size()-1 ? '\n' : ' ');
    	puts("");
    }
    return 0;
}

Read More +

Jun 24 2014

解題區►解題區 - UVa

UVa 11837 - Musical Plagiarism

Problem

The musical notes are the basic units of Western music. Each note is associated with a frequency. Two notes for which the fundamental frequencies have a ratio of power of 2 (one is half of the other, one is double of the other, etc..) are perceived as very similar. Therefore, any notes with that kind of relationship are given the same name, as described below.

There are twelve basic notes in a sequence of increasing frequency, each note separated from the previous note by the same distance in the musical scale (this distance is called a semitone). Seven of these twelve notes are represented by letters of the alphabet (A, B, C, D, E, F and G). The table below shows the distance, in semitones, between the notes.

Notes A-B B-C C-D D-E E-F F-G G-A
Number of semitone 2 1 2 2 1 2 2

Notice that there are five notes that are not represented by letters of the alphabet: the notes between A and B, between C and D, between D and E, betwen F and G and between G and A.

Notes can be modified by two accidentals, called sharp and flat, represented respectively by the symbols #' andb’. A sharp raises the note a semitone, a flat lowers the note a semitone. A note with an accidental is denoted by the name of the note followed by the accidental symbol. Notice that with this scheme we can represent all twelve notes.

The figure below illustrates the name of the notes in accordance with the scheme described above, in a fragment of a piano keyboard.

A melody can be represented by a sequence of notes. For example,

A A D C# C# D E E E F# A D G# A

is a well known melody. Note however that as the distances between the semitones are always equal, the same melody can be written starting with another note (we say that the melody is in another key):

B B E D# D# E Gb Gb Gb G# B E A# B

Your neighbor is a famous composer who suspects someone has plagiarized one of her songs. She asked your help to write a program that, given the sequence of notes of the melody in her song, and the sequence of notes of a suspicious snippet of melody, determines if the suspicious snippet occurs, in some key, in her song.

Input

The input consists of several test cases. The first line of a test case contains two integers M and T ( 1$ \le$M$ \le$105, 1$ \le$T$ \le$104, T$ \le$M), indicating the number of notes in the song suspected of having been plagiarized and in the suspect snippet. Each of the next two lines contains M and T notes, respectively, indicating the notes of the song and of the suspect snippet.

Notes in each line are separated by one space; each note is one among A',B’, C',D’, E',F’ or G', possibly followed by an accidental sign:#’ for sharp or `b’ for flat.

The last test case is followed by a line containing only two zeros separated by a blank space.

Output

For each test case your program must print a single line containing one character, S' in case the song has been plagiarized by the text, orN’ in case the song has not been plagiarized by the text.

Sample Input

16 4
D G A B C D G G G C D E F# G C C
G G C D
12 2
C C# D D# E F F# G G# A A# B
C D
12 2
C Db D Eb E F Gb G Ab A Bb B
C D
4 3
C E G Bb
D F# A
0 0

Sample Output

S
N
N
S

Solution

題目描述：

音階全全半全全全半，全音中間夾一個黑/白鍵，半音之間沒有。

計算是否為旋律中的一部分，計算旋律時只需考慮音符之間的距離即可，與高低幾度偏移沒有關係。

題目解法：

特別小心，查詢的旋律長度為 1 的時候，無法判斷 (雖然以子字串是有在的)。

接著，直接對距離之間取模之後得到兩個整數序列，直接套用 KMP 判斷序列是否在另一個序列中。

#include <stdio.h>
#include <algorithm>
using namespace std;
int notes[128] = {};
int kmpTable[500005];
void KMPtable(int *P, int len) {
    int i, j;
    kmpTable[0] = -1, i = 1, j = -1;
    while(i < len) {
        while(j >= 0 && P[j+1] != P[i])
            j = kmpTable[j];
        if(P[j+1] == P[i])
            j++;
        kmpTable[i++] = j;
    }
}
int KMPmatching(int T[], int P[], int tlen, int plen) {
    for(int i = 0, j = -1; i < tlen; i++) {
        while(j >= 0 && P[j+1] != T[i])
            j = kmpTable[j];
        if(P[j+1] == T[i])  j++;
        if(j == plen-1) {
            j = kmpTable[j];
            return i;
        }
    }
    return -1;
}
int main() {
	int M, T;
	int A[100005], B[10005];
	char s[10];
	notes['C'] = 0, notes['D'] = 2;
	notes['E'] = 4,	notes['F'] = 5;
	notes['G'] = 7,	notes['A'] = 9;
	notes['B'] = 11;
	while(scanf("%d %d", &M, &T) == 2 && M + T) {
		int prev, x;
		for(int i = 0; i < M; i++) {
			scanf("%s", &s);
			x = (notes[s[0]] + (s[1] == '#') - (s[1] == 'b') + 12)%12;
			if(i)	A[i - 1] = (prev - x + 12)%12;
			prev = x;
		}
		for(int i = 0; i < T; i++) {
			scanf("%s", &s);
			x = (notes[s[0]] + (s[1] == '#') - (s[1] == 'b') + 12)%12;
			if(i)	B[i - 1] = (prev - x + 12)%12;
			prev = x;
		}
		KMPtable(A, M - 1);
		puts( KMPmatching(A, B, M - 1, T - 1) >= 0 ? "S" : "N");
	}
	return 0;
}

Read More +

Jun 24 2014

解題區►解題區 - UVa

UVa 198 - Peter's Calculator

Problem

Unfortunately, Peter’s Calculator broke down last week. Now Peter is left with his computer, which has no calculator application, and paper and pencil, which is too tiresome for an engineer. As one of Peter’s friends, you are asked to write him a calculator application. After talking to him, you figure out the following:

Peter does only integer arithmetic. The operations he needs are addition, subtraction and multiplication.
He would like to use an arbitrary number of variables whose names are not longer than 50 characters.
His main way of doing calculations are to type in a few formulas and to assign them to variables. Some formulas are complicated expressions, which can refer to yet undefined variables, while other formulas consist of a single number. Then Peter asks for the value of some variables, i.e. he evaluates the formulas.
Peters wants to redefine some variables and then to reevaluate formulas that depend on these variables.

The input strictly adheres to the following syntax (given in EBNF):

file = line { line } <EOF>.
line = [ assignment | print | reset ] <CR>.
assignment = var ":=" expression.
print = "PRINT" var.
reset = "RESET".
expression = term { addop term }.
term = factor { mulop factor }.
factor = "(" expression ")" | var | number.
addop = "+" | "-".
mulop = "*".

In the Extended Backus-Naur Formalism (EBNF), A = B C declares that the grammatical construct A consists of a B followed by a C . A = B | C means that A consists of a B or, alternatively, of a C . A = [ B ] defines construct A to be either a B or nothing and A = B tells you that A consists of the concatenation of any number of B’s (including none).

The production var stands for the name of a variable, which starts with a letter followed by up to 49 letters or digits. Letters may be uppercase or lowercase. The production number stands for a integer number. The precise syntax for these productions are given below. The case of letters is important for both variables and statements.

var = letter { letter | digit }.
number = [ "-" ] digit { digit }.
letter = "A" | "B" | ... | "Z" | "a" | "b" | ... | "z".
digit = "0" | "1" | ... | "8" | "9".

Between the parts of a grammatical construct but not within the names of variables or integer numbers, any number of spaces may appear. stands for the end of the input file and stands for the new-line character. All lines in the input file are shorter than 200 characters.

The value of a variable is said to be undefined:

if it has not yet been defined or it refers to a variable, which has not yet been defined;
if the definition of the variable contains a cycle.

Your are to write a program that implements Peter’s calculator. It should store all variable definitions and for each “PRINT” statement evaluate the specified variable based on the latest variable definitions. If your program encounters a “RESET” statement, it should delete all stored variables so that all variables become undefined.

Input

The input file contains calculations adhering to the syntax given above. Each line contains either an assignment to a variable, a “PRINT” statement, a “RESET” statement or nothing.

Output

For each “PRINT” statement found in the input file, your program should output a line containing the numerical value of the specified variable or the word “UNDEF” if the variable is undefined.

Sample Input

a := b + c
b := 3
c := 5
PRINT d
PRINT a
b := 8
PRINT a
RESET
PRINT a

Sample Output

UNDEF
8
13
UNDEF

Solution

題目描述：

輸入有一連串的變數函數，適時地打印出詢問的變數值，如果存在循環依靠 (無法推論) 或者是變數尚未定義，直接輸出 UNDEF。

後輸入的變數函數會覆蓋原先的函數。

題目解法：

將每一組函數轉成後序運算式子，爾後再使用深度優先搜索走訪查看是否有環。

著重的問題在於負數的分析，例如 0 - -50, (a + b) - 50 等等。

#include <stdio.h>
#include <stack>
#include <string.h>
#include <algorithm>
#include <ctype.h>
#include <iostream>
#include <sstream>
#include <map>
using namespace std;
int priority_op(char c) {
    switch(c) {
        case '(':return 0;
        case '+': case '-':return 1;
        case '*': case '/':return 2;
    }
    return -1;
}
int isoperator(char c) {
    switch(c) {
        case '(':case ')':case '+': case '-':case '*': case '/':return 1;
    }
    return 0;
}
int isvariable(string token) {
	return isalpha(token[0]);
}
void trans(const char *infix, char buffer[]) {
    int len = strlen(infix), prevOp = 1;
    char *ptr = buffer;
    stack<char> op;
    *ptr = '\0';
    for(int i = 0; i < len; i++) {
        if(isalpha(infix[i]) || isdigit(infix[i]) 
			|| (infix[i] == '-' && isdigit(infix[i+1]) && prevOp)) {
			prevOp = 0;
        	sprintf(ptr, "%c", infix[i]), i++;
        	while(*ptr)    ptr++;
			while(isalpha(infix[i]) || isdigit(infix[i])) {
            	sprintf(ptr, "%c", infix[i]), i++;
            	while(*ptr)    ptr++;
            }
            sprintf(ptr, " "), i--;
            while(*ptr)		ptr++;
        } else {
        	prevOp = 0;
            if(infix[i] == ')') {
                while(!op.empty() && op.top() != '(') {
                    sprintf(ptr, "%c ", op.top()), op.pop();
                    while(*ptr) ptr++;
                }
                op.pop();
            } else {
                if(infix[i] != '(') {
	                while(!op.empty() && priority_op(op.top()) >= priority_op(infix[i])) {
	                    sprintf(ptr, "%c ", op.top()), op.pop();
	                    while(*ptr) ptr++;
	                }
            	}
	        	prevOp = 1;
                op.push(infix[i]);
            }
        }
    }
    while(!op.empty()) {
        sprintf(ptr, "%c ", op.top()), op.pop();
        while(*ptr) ptr++;
    }
}
void trimWhiteSpace(char s[]) {
	int j = 0;
	for(int i = 0; s[i]; i++)
		if(!isspace(s[i]))
			s[j++] = s[i];
	s[j] = '\0';
}
map<string, string> VAL_exp;
map<string, int>	VAL_val;
map<string, int>	VAL_stk;
int error_FLAG;
int calcPostfix(const char* postfix);
int getValue(string VAL_name) {
    if(!isvariable(VAL_name)) {
    	stringstream scin(VAL_name);
    	int value;
    	scin >> value;
    	return value;
    }
	if(VAL_exp.find(VAL_name) == VAL_exp.end() || VAL_stk[VAL_name]) {
		error_FLAG = 1;
		return 0;
	}
	if(VAL_val.find(VAL_name) == VAL_val.end()) {
		VAL_stk[VAL_name] = 1;
//		cout << "solving " << VAL_name << ", " << VAL_exp[VAL_name] << endl; 
		VAL_val[VAL_name] = calcPostfix(VAL_exp[VAL_name].c_str());
//		cout << "solved " << VAL_name << ", val = " << VAL_val[VAL_name] << endl;
		VAL_stk[VAL_name] = 0;
	}
	return VAL_val[VAL_name];
}
int calcPostfix(const char* postfix) {
	stringstream 	scin(postfix);
    stack<int> 		stk;
	string			token;
    int 			a, b;
    
    while(scin >> token) {
    	if(token.length() == 1 && isoperator(token[0])) {
            b = stk.top(), stk.pop();
            a = stk.top(), stk.pop();
            switch(token[0]) {
                case '+': a = a+b;break;
                case '-': a = a-b;break;
                case '*': a = a*b;break;
                case '/': a = a/b;break;
            }
            stk.push(a);
    	} else {
    		stk.push(getValue(token));
    	}
    	if(error_FLAG)	return 0;
    }
    return stk.top();
}
void printVal(string valName) {
	error_FLAG = 0;
	VAL_val.clear();
	VAL_stk.clear();
	int val = getValue(valName);
	if(error_FLAG)
		puts("UNDEF");
	else
		printf("%d\n", val);
}
int main() {
//	freopen("input.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
	string 	LHS, RHS;
	int 	pos;
	char 	postfix[32767], lines[32767];
	
    while(gets(lines)) {
    	trimWhiteSpace(lines);
    	string str(lines);
    	if(str.find(":=") != string::npos) {
    		pos = str.find(":=");
    		LHS = str.substr(0, pos);
    		RHS = str.substr(pos + 2);
    		trans(RHS.c_str(), postfix);
    		VAL_exp[LHS] = postfix;
    	} else if(str.find("PRINT") != string::npos) {
    		pos = str.find("PRINT");
    		RHS = str.substr(pos + 5);
    		printVal(RHS);
    	} else if(str.find("RESET") != string::npos) {
    		VAL_exp.clear();
    	}
    }
    return 0;
}

Read More +

Jun 24 2014

解題區►解題區 - UVa

UVa 11178 - Morley's Theorem

Problem

Morley’s theorem states that that the lines trisecting the angles of an arbitrary plane triangle meet at the vertices of an equilateral triangle. For example in the figure below the tri-sectors of angles A, B and C has intersected and created an equilateral triangle DEF.

Of course the theorem has various generalizations, in particular if all of the tri-sectors are intersected one obtains four other equilateral triangles. But in the original theorem only tri-sectors nearest to BC are allowed to intersect to get point D, tri-sectors nearest to CA are allowed to intersect point E and tri-sectors nearest to AB are intersected to get point F. Trisector like BD and CE are not allowed to intersect. So ultimately we get only one equilateral triangle DEF. Now your task is to find the Cartesian coordinates of D, E and F given the coordinates of A, B, and C.

Input

First line of the input file contains an integer N (0<N<5001) which denotes the number of test cases to follow. Each of the next lines contain six integers . This six integers actually indicates that the Cartesian coordinates of point A, B and C are respectively. You can assume that the area of triangle ABC is not equal to zero, and the points A, B and C are in counter clockwise order.

Output

For each line of input you should produce one line of output. This line contains six floating point numbers separated by a single space. These six floating-point actually means that the Cartesian coordinates of D, E and F are respectively. Errors less than will be accepted.

Sample Input

1
2
3

2
1 1 2 2 1 2
0 0 100 0 50 50

Output for Sample Input

1 2	1.316987 1.816987 1.183013 1.683013 1.366025 1.633975 56.698730 25.000000 43.301270 25.000000 50.000000 13.397460

Solution

題目描述：

給一個三角形，將每一個角三等分後，交三角形內部三個點，求這三個點座標。

題目解法：

向量旋轉、射線交點。

射線交點的部分採用最簡單的克拉瑪方程求解。

#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
	Pt operator-(const Pt &a) const {
		Pt ret;
		ret.x = x - a.x;
		ret.y = y - a.y;
        return ret;
    }
};
double dist(Pt a, Pt b) {
	return hypot(a.x - b.x, a.y - b.y);
}
double length(Pt a) {
	return hypot(a.x, a.y);
}
double dot(Pt a, Pt b) {
	return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
	return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
double angle(Pt a, Pt b) {
	return acos(dot(a, b) / length(a) / length(b));
}
Pt rotateRadian(Pt a, double radian) {
	double x, y;
	x = a.x * cos(radian) - a.y * sin(radian);
	y = a.x * sin(radian) + a.y * cos(radian);
	return Pt(x, y);
}
Pt getIntersection(Pt p, Pt l1, Pt q, Pt l2) {
	double a1, a2, b1, b2, c1, c2;
	double dx, dy, d;
	a1 = l1.y, b1 = -l1.x, c1 = a1 * p.x + b1 * p.y;
	a2 = l2.y, b2 = -l2.x, c2 = a2 * q.x + b2 * q.y;
	d = a1 * b2 - a2 * b1;
	dx = b2 * c1 - b1 * c2;
	dy = a1 * c2 - a2 * c1;
	return Pt(dx / d, dy / d);
}
Pt solve(Pt A, Pt B, Pt C) {
	double radABC = angle(A - B, C - B);
	double radACB = angle(A - C, B - C);
	
	Pt vB = rotateRadian(C - B, radABC /3);
	Pt vC = rotateRadian(B - C, - radACB /3);
	
	return getIntersection(B, vB, C, vC);
}
int main() {
	int testcase;
	scanf("%d", &testcase);
	while(testcase--) {
		Pt A, B, C, D, E, F;
		scanf("%lf %lf", &A.x, &A.y);
		scanf("%lf %lf", &B.x, &B.y);
		scanf("%lf %lf", &C.x, &C.y);
		D = solve(A, B, C);
		E = solve(B, C, A);
		F = solve(C, A, B);
		printf("%lf %lf %lf %lf %lf %lf\n", D.x, D.y, E.x, E.y, F.x, F.y);
	}
	return 0;
}

Read More +

Jun 24 2014

解題區►解題區 - UVa

UVa 427 - FlatLand Piano Movers

Problem

FlatLand Piano Movers, as part of their Total Quality Management project, has decided to focus on the job estimation process. Part of this process involves walking the proposed paths that are to be used to move a piano to see if it will fit through corridors and around corners. Now this is harder than it might seem, since FlatLand is a 2-dimensional world.

FlatLand pianos are rectangles of various sizes. FlatLand building codes require all turns in corridors to be right angle turns and prohibit T intersections. All dimensions are in furlongs. You can assume that each portion of a corridor is long enough so that other corners or doors into rooms don’t have any effect on getting around a turn. You can also assume that the piano is narrower than the width of any corridor. Note that the piano actually has to turn in the corner, since it can only be pushed or pulled on one of its shorter sides (there are no square pianos).

Your team’s job is to write a program for a palmtop computer that will determine if a given piano will fit around a corner in a corridor.

Input

The input consists of a series of lines up to 80 columns in width followed by the end-of-file. Each line consists of a series of number pairs. The numbers of a pair are separated by a comma and the pairs are separated by at least one space. The first pair is the size of a piano, and the remaining pairs are the widths of corridors on each side of the turns. Consider the example:

1	600,200 300,500 837,500 350,350

This is a 600 by 200 piano. The first turn is from a 300 furlong wide corridor through a right angle turn into a 500 furlong wide corridor. The next turn is from an 837 furlong wide corridor into one 500 furlongs wide. The last turn is from a 350 furlong wide corridor into another 350 furlong wide corridor.

Output

For each piano, your program is to produce a yes-or-no answer for each turn. If the piano will fit around the turn, print Y''; if not, printN’’. The results for each piano should be printed on a separate line.

Sample Input

1 2	600,200 300,500 837,500 350,350 137,1200 600,500 600,400

Sample Output

1
2

YYN
YN

Solution

題目描述：

一台鋼琴長寬 W, H，接著要經過一個 T 字路口，進去之後向右轉，一開始進去的寬度為 X，右轉之後的寬度為 Y，問能不能順利轉彎。

每組輸入給定一台鋼琴長寬，接著給定多組路口寬組合。

題目解法：

汽车拐弯问题，给定 X, Y, l, d 判断是否能够拐弯。首先当 X 或者 Y 小于 d，那么一定不能。
其次我们发现随着角度 θ 的增大，最大高度 h 先增长后减小，即为凸性函数，可以用三分法来求解。

这里的 Calc 函数需要比较繁琐的推倒公式：
s = l cos(θ) + w sin(θ) - x;
h = s tan(θ) + w cos(θ);
其中 s 为汽车最右边的点离拐角的水平距离, h 为里拐点最高的距离, θ 范围从 0 到 90。

轉貼備份www.cnblogs.com/newpanderking/…

看著大神給的三分搜索的式子，用簡單的凸性勾勒出來。

#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
// http://www.cnblogs.com/newpanderking/archive/2011/08/25/2153777.html
const double pi = acos(-1);
#define eps 1e-6 
double ternary_search(double H, double W, double X, double Y) {
	double l = 0, r = pi /2, mid, midmid;
	double s1, h1, s2, h2;
	while(fabs(l - r) > eps) {
		mid = (l + r) /2;
		midmid = (mid + r) /2;
		s1 = H * cos(mid) + W * sin(mid) - X;
		h1 = s1 * tan(mid) + W * cos(mid);
		s2 = H * cos(midmid) + W * sin(midmid) - X;
		h2 = s2 * tan(midmid) + W * cos(midmid);
		if(h1 < h2)
			l = mid;
		else
			r = mid;
	}
	return h1;
}
int main() {
	char line[1024];
	while(gets(line)) {
		stringstream sin(line);
		string token;
		sin >> token;
		double H, W, X, Y;
		sscanf(token.c_str(), "%lf,%lf", &H, &W);
		if(H < W)
			swap(H, W);
		while(sin >> token) {
			sscanf(token.c_str(), "%lf,%lf", &X, &Y);
			double h = ternary_search(H, W, X, Y);
			printf("%c", h <= Y ? 'Y' : 'N');
		}
		puts("");
	}
	return 0;
}

Read More +

Jun 24 2014

解題區►解題區 - UVa

UVa 174 - Strategy

Problem

A well known psychology experiment involves people playing a game in which they can either trade with each other or attempt to cheat the other player. If both players TRADE then each gains one point. If one TRADEs and the other CHEATs then the TRADEr loses 2 points and the CHEATer wins 2. If both CHEAT then each loses 1 point.

There are a variety of different strategies for playing this game, although most people are either unable to find a winning strategy, or, having decided on a strategy, do not stick to it. Thus it is fairer to attempt to evaluate these strategies by simulation on a computer. Each strategy is simulated by an automaton. An automaton is characterised by a program incorporating the strategy, a memory for previous encounters and a count reflecting the score of that automaton. The count starts at zero and is altered according to the above rules after each encounter. The memory is able to determine what happened on up to the last two encounters with each other contender.

Write a program that will read in details of up to 10 different strategies, play each strategy against each other strategy 10 times and then print out the final scores. Strategies will be in the form of simple programs obeying the following grammar:

<program> ::= <statement>.
<statement> ::= <command> tex2html_wrap_inline45 <ifstat>
<ifstat> ::= IF <condition> THEN <statement> ELSE <statement>
<condition> ::= <cond> tex2html_wrap_inline45 <cond> <op> <condition>
<op> ::= AND tex2html_wrap_inline45 OR
<cond> ::= <memory> {= tex2html_wrap_inline45 #} {<command> tex2html_wrap_inline45 NULL}
<memory> ::= {MY tex2html_wrap_inline45 YOUR} LAST {1 tex2html_wrap_inline45 2}
<command> ::= TRADE tex2html_wrap_inline45 CHEAT

Note that LAST1 refers to the previous encounter between these two automata, LAST2 to the encounter before that and that MY' andYOUR’ have the obvious meanings. Spaces and line breaks may appear anywhere in the program and are for legibility only. The symbol #' meansis not equal to’. NULL indicates that an encounter has not ocurred. The following are valid programs:

CHEAT.
IF MY LAST1 = CHEAT THEN TRADE ELSE CHEAT.
IFYOURLAST2=NULLTHENTRADEELSEIFYOURLAST1=TRADETHENTRADE
ELSECHEAT.

Input

Input will consist of a series of programs. Each program will be no longer than 255 characters and may be split over several lines for convenience. There will be no more than 10 programs. The file will be terminated by a line containing only a single `#’.

Output

Output will consist of one line for each line of input. Each line will consist of the final score of the relevant program right justified in a field of width 3.

Sample input

CHEAT.
IF MY LAST1 = CHEAT THEN TRADE ELSE CHEAT.
IFYOURLAST2=NULLTHENTRADEELSEIFYOURLAST1=TRADETHENTRADE
ELSECHEAT.
#

Sample output

1
2
3

  1
-12
-13

Solution

題目描述：

現在這邊有兩台機器人，玩類似 “吹牛” 的紙牌遊戲，欺騙成功者將獲得點數。

而每一台機器的策略也有所不同，並且能根據對方前幾次和自己前幾次的策略進行判斷，給予每一台機器的策略模式，請兩兩互打 10 回合，最後輸出每一台機器的得分概況。

題目解法：

這題不只有語法分析，還有語意分析。總之，遞迴分析是最主要的技巧。
對於 AND 和 OR 運算，測資中似乎沒有優先順序的情況，所以直接由左而右進行即可。

而在分析的時候，嘗試將指針一直往後移動，並且解析出第一個符合條件的 token。

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <math.h>
#include <iostream>
#include <map>
#include <assert.h>
#include <string.h>
#include <ctype.h>
using namespace std;
enum ACTION {TRADE, CHEAT, EMPTY};
enum RECORD {LAST1, LAST2};
class Memory {
public:
    map<RECORD, ACTION> R;
    Memory() {
        R[LAST1] = EMPTY;
        R[LAST2] = EMPTY;
    }
    static ACTION getAction(string s) {
        if(s == "TRADE")    return TRADE;
        if(s == "CHEAT")    return CHEAT;
        if(s == "EMPTY")    return EMPTY;
        assert(false);
    }
    ACTION getMemory(string addr) {
        if (addr == "LAST1")
            return R[LAST1];
        if (addr == "LAST2")
            return R[LAST2];
        assert(false);
    }
    void record(ACTION a) {
        ACTION last1 = R[LAST1], last2 = R[LAST2];
        R[LAST1] = a;
        R[LAST2] = last1;
    }
};
class Strategy {
public:
    char prog[1024];
    Strategy(string s) {
        for (int i = 0; i < s.length(); i++) {
            prog[i] = s[i];
        }
        prog[s.length()] = '\0';
    }
    char* match(char *str, const char *p) {
        if (str == NULL)
            return  NULL;
        if (memcmp(str, p, strlen(p)) == 0)
            return str + strlen(p);
        return NULL;
    }
/*
 <condition> ::= <cond> | <cond> <op> <condition>
 <op> ::= AND | OR
 <cond> ::= <memory> {= | #} {<command> | NULL}
 <memory> ::= {MY | YOUR} LAST {1 | 2}
 <command> ::= TRADE | CHEAT
 */
    bool cond(char* &p, Memory MY, Memory YOUR) {
        // printf("condition %s\n", p);
        char        *q;
        Memory      *addr = NULL;
        string      read, equal, kind;
        /* <memory> */
        q = match(p, "MY");
        if(q != NULL)   p = q, addr = &MY;
        q = match(p, "YOUR");
        if(q != NULL)   p = q, addr = &YOUR;
        q = match(p, "LAST1");
        if(q != NULL)   p = q, read = "LAST1";
        q = match(p, "LAST2");
        if(q != NULL)   p = q, read = "LAST2";
        /* {= | #} */
        q = match(p, "=");
        if(q != NULL)   p = q, equal = "=";
        q = match(p, "#");
        if(q != NULL)   p = q, equal = "#";
        /* {<command> | NULL} */
        q = match(p, "TRADE");
        if(q != NULL)  p = q, kind = "TRADE";
        q = match(p, "CHEAT");
        if(q != NULL)  p = q, kind = "CHEAT";
        q = match(p, "NULL");
        if(q != NULL)  p = q, kind = "EMPTY";
        bool ret = equal == "=" ? addr->getMemory(read) == Memory::getAction(kind) :
									addr->getMemory(read) != Memory::getAction(kind);
        // cout << "ADDR: " << addr->getMemory(read) << ", ACTION: " << Memory::getAction(kind) << endl;
        // cout << read << ", " << kind << endl; 
        /* <op> <condition> */
        q = match(p, "AND");
        if(q != NULL)  p = q, ret = ret&cond(p, MY, YOUR);
        q = match(p, "OR");
        if(q != NULL)  p = q, ret = ret|cond(p, MY, YOUR);
        // cout << "return " << ret << endl;
        return ret;
    }
    ACTION ifstat(char* &p, Memory a, Memory b) {
        char *q;
        q = match(p, "IF");
        if (q != NULL) {
            p = q;
            bool f = cond(p, a, b);
            ACTION a1, a2;
            q = match(p, "THEN");
            p = q;
            a1 = statement(p, a, b);
            q = match(p, "ELSE");
        	p = q;
        	a2 = statement(p, a, b);
        	return f ? a1 : a2;
        }
        assert(false);
    }
    ACTION statement(char* &p, Memory a, Memory b) {
        // printf("%s\n", p);
        char *q;
        q = match(p, "TRADE");
        if (q != NULL)  {
            p = q;
            return TRADE;
        }
        q = match(p, "CHEAT");
        if (q != NULL) {
            p = q;
            return CHEAT;
        }
        return ifstat(p, a, b);
    }
    ACTION eval(char* &p, Memory a, Memory b) { // read only
        // printf("eval %s\n", p);
        return statement(p, a, b);
    }
};
int main() {
    char c, s[1024];
    vector<Strategy> machine;
    while (true) {
        int n = 0;
        while ((c = getchar()) != EOF) {
            if(c == '.' || (c == '#' && n == 0) )
                break;
            if(isspace(c))
                continue;
            s[n++] = c;
        }
        if (n == 0)
            break;
        s[n++] = '\0';
        machine.push_back(Strategy(s));
    }
#define MAXN 20
    int SCORE[MAXN] = {};
    for (int i = 0; i < machine.size(); i++) {
        for (int j = i + 1; j < machine.size(); j++) {
            Memory      ma, mb;
            Strategy    &A = machine[i];
            Strategy    &B = machine[j];
            char        *p;
            
            for (int k = 0; k < 10; k++) {
                ACTION ia = A.eval(p = A.prog, ma, mb);
                ACTION ib = B.eval(p = B.prog, mb, ma);
                if(ia == TRADE && ib == TRADE)
                	SCORE[i]++, SCORE[j]++;
                else if(ia == TRADE && ib == CHEAT)
                	SCORE[i] -= 2, SCORE[j] += 2;
                else if(ia == CHEAT && ib == TRADE)
                	SCORE[i] += 2, SCORE[j] -= 2;
                else
                	SCORE[i]--, SCORE[j]--;
                ma.record(ia), mb.record(ib);
            }
        }
    }
    for(int i = 0; i < machine.size(); i++)
    	printf("%3d\n", SCORE[i]);
    return 0;
}

Read More +

Jun 24 2014

解題區►解題區 - UVa

UVa 171 - Car Trialling

Problem

Car trialling requires the following of carefully worded instructions. When setting a trial, the organiser places traps in the instructions to catch out the unwary.

Write a program to determine whether an instruction obeys the following rules, which are loosely based on real car trialling instructions. BOLD-TEXT indicates text as it appears in the instruction (case sensitive), | separates options of which exactly one must be chosen, and .. expands, so A..D is equivalent to A | B | C | D .

instruction = navigational | time-keeping | navigational AND time-keeping
navigational = directional | navigational AND THEN directional
directional = how direction | how direction where
how = GO | GO when | KEEP
direction = RIGHT | LEFT
when = FIRST | SECOND | THIRD
where = AT sign
sign = "signwords"
signwords = s-word | signwords s-word
s-word = letter | s-word letter
letter = A..Z | .
time-keeping = record tex2html_wrap_inline61 change
record = RECORD TIME
change = cas TO nnn KMH
cas = CHANGE AVERAGE SPEED | CAS
nnn = digit | nnn digit

digit = 0..9 Note that s-word and nnn are sequences of letters and digits respectively, with no intervening spaces. There will be one or more spaces between items except before a period (.), after the opening speech marks or before the closing speech marks.

Input

Each input line will consist of not more than 75 characters. The input will be terminated by a line consisting of a single #.

Output

The output will consist of a series of sequentially numbered lines, either containing the valid instruction, or the text Trap! if the line did not obey the rules. The line number will be right justified in a field of 3 characters, followed by a full-stop, a single space, and the instruction, with sequences of more than one space reduced to single spaces.

Sample input

KEEP LEFT AND THEN GO RIGHT
CAS TO 20 KMH
GO FIRST       RIGHT AT "SMITH ST."  AND   CAS TO 20 KMH
GO 2nd RIGHT
GO LEFT AT "SMITH STREET AND RECORD TIME
KEEP RIGHT AND THEN RECORD TIME
#

Sample output

1. KEEP LEFT AND THEN GO RIGHT
2. CAS TO 20 KMH
3. GO FIRST RIGHT AT "SMITH ST." AND CAS TO 20 KMH
4. Trap!
5. Trap!
6. Trap!

Solution

題目描述：

根據題目給定的規則，將汽車引領的命令句子做合法語句判斷。

題目解法：

根據編譯器的方式，採用 LL(1) 修改題目給定的規則後，要進行建表，但是發現有幾處無法排除的語法規則，之後採用 SLR(1) 來完成。

SLR(1) 是由 LR(0) 加上 follow set 完成。

詳細的運作過程請詳見 wiki 說明，或者是修編譯器。

1	There will be one or more spaces between items except before a period (.), after the opening speech marks or before the closing speech marks.

本題最邪惡的地方在這裡，句號（.）前不可以用空白，前雙引號後不可有空白、後雙引號前不可以有空白。

雖然題目有包含這些 token 的語法產生，但還是用最暴力的方式將句子做基礎的 token 切割。

#include <stdio.h> 
#include <vector>
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string.h>
#include <ctype.h>
#include <assert.h>
using namespace std;
#define HTMLProduction
// #define DEBUG
class Production {
	public:
		int 			label;
		string 			LHS;
		vector<string> 	RHS;
		
		Production(string L = "", vector<string> R = vector<string>(), int l=0) {
			LHS = L;
			RHS = R;
			label = l;
		}
		bool operator<(const Production &p) const {
			if(LHS != p.LHS)
				return LHS < p.LHS;
			for(size_t i = 0, j = 0; i < RHS.size() && j < p.RHS.size(); i++, j++) {
				if(RHS[i] != p.RHS[i])
					return RHS[i] < p.RHS[i];
			}
			return RHS.size() < p.RHS.size();
		}
		
		bool operator==(const Production &p) const {
			if(LHS != p.LHS || RHS.size() != p.RHS.size())
				return false;
			for(size_t i = 0, j = 0; i < RHS.size(); i++, j++) {
				if(RHS[i] != p.RHS[i])
					return false;
			}
			return true;
		}
		
		bool operator!=(const Production &p) const {
			return !(*this == p);
		}
		
		void print() {
			printf("%s -> ", LHS.c_str());
			for(size_t i = 0; i < RHS.size(); i++)
				printf("%s", RHS[i].c_str());
		}
};
class Grammar {
	public:
		/* LR parsing */
		class ConfigurationSet {
			public:
				class State {
					public:
						int dot;
						vector<string> lookahead;
						
						State(int d=0, vector<string> l=vector<string>()):
							dot(d), lookahead(l) {}
						bool operator<(const State &x) const {
							return dot < x.dot;
						}
						bool operator!=(const State &x) const {
							return dot != x.dot;
						}
				};
				
				set< pair<Production, State> > 	configs;
				int 							label;
				ConfigurationSet() {
					label = 0;
				}
				/* method */
				static ConfigurationSet closure0(ConfigurationSet& s, Grammar& g);
				static ConfigurationSet go_to0(ConfigurationSet& s, string X, Grammar& g);
				void print(Grammar &g) {
					set< pair<Production, State> >::iterator it;
					Production p;
					
					for(it = configs.begin(); it != configs.end(); it++) {
						p = it->first;
						printf("%s ->", p.LHS.c_str());
						for(size_t i = 0; i < p.RHS.size(); i++) {
							if(i == it->second.dot)
								printf("¡E");
							printf(" %s ", p.RHS[i].c_str());
						}
						if(it->second.dot == p.RHS.size())
							printf("¡E");
						printf(" ,{");
						set<string> fset = g.follow_set[p.LHS];
						for(set<string>::iterator jt = fset.begin();
							jt != fset.end(); jt++) {
							if(jt != fset.begin())
								cout << ", ";
							cout << *jt;
						}
						printf("}");
						puts("");
					}
				}
				bool operator<(const ConfigurationSet &x) const {
					if(configs.size() != x.configs.size())
						return configs.size() < x.configs.size();
					for(set< pair<Production, State> >::iterator it = configs.begin(), jt = x.configs.begin();
						it != configs.end(); it++, jt++) {
						if(it->first != jt->first)
							return it->first < jt->first;
						if(it->second != jt->second)
							return it->second < jt->second;
					}
					return false;
					// return label < x.label;
				}
		};		
		
		static const string 		lambda;
		set<string>					symbols;
		string 						start_symbol;
		vector<Production> 			rules;
		/* LL(1) attribute */
		map<string, set<string> > 	first_set;
		map<string, set<string> > 	follow_set;
		map<string, bool> 			derives_lambda;
		map<string, map<string, Production> >	lltable;
		/* LR attribute */
		vector<ConfigurationSet>	LRstates;
		map<int, map<string, int> >	go_to_table;
		map<int, int>				action_table;
		
		/* common method */
		static bool isNonterminal(string token);
		void buildSymbols();
		/* LL(1) method */
		map<string, bool> mark_lambda();
		void fill_first_set();
		void fill_follow_set();
		set<string> compute_first(vector<string> rhs);
		set<string> get_predict_set(Production p);
		void fill_lltable();
		void lldriver(queue<string> tokens);
		/* LR method*/
		void build_CFSM();
		void build_action();
		void lr0driver(queue<string> tokens);
		int slr1driver(queue<string> tokens);
		void lalr1driver(queue<string> tokens);
		/* homework */
		void hw_build_CFSM();
};
/* ------------------------
ConfigurationSet method
-------------------------- */
Grammar::ConfigurationSet Grammar::ConfigurationSet::closure0(ConfigurationSet& s, Grammar& g) {
	ConfigurationSet 	r = s;
	bool				changes;
	string				A;
	Production			P;
	int 				dotPos;
	
	set< pair<Production, State> >::iterator it;
	do {
		changes = false;
		for(it = r.configs.begin(); it != r.configs.end(); it++) {
			P = it->first;
			dotPos = it->second.dot;
			if(dotPos >= P.RHS.size() || P.RHS[dotPos] == Grammar::lambda)
				continue;
			A = P.RHS[dotPos];
			if(Grammar::isNonterminal(A)) {
				/* B -> x.Ay */
				/* Predict productions with A as the left-hand side */
				for(size_t i = 0; i < g.rules.size(); i++) {
					if(g.rules[i].LHS == A) {
						if(r.configs.find(make_pair(g.rules[i], State(0))) == r.configs.end()) {
							r.configs.insert(make_pair(g.rules[i], State(0)));
							changes = true;
						}
					}
				}
			}
		}
	} while(changes);
	return r;
}
Grammar::ConfigurationSet Grammar::ConfigurationSet::go_to0(ConfigurationSet& s, string X, Grammar& g) {
	ConfigurationSet sb;
	set< pair<Production, State> >::iterator it;
	Production 	P;
	int 		dotPos;
	
	for(it = s.configs.begin(); it != s.configs.end(); it++) {
		P = it->first;
		dotPos = it->second.dot;
		if(dotPos >= P.RHS.size() || P.RHS[dotPos] == Grammar::lambda)
			continue;
		if(P.RHS[dotPos] == X) {
			State state(dotPos + 1, it->second.lookahead);
			sb.configs.insert(make_pair(P, state));
		}
	}
	return closure0(sb, g);
}
/* ------------------------
Grammar method
-------------------------- */
const string Grammar::lambda("l");
set<string> Grammar::compute_first(vector<string> rhs) {
	set<string> result;
	size_t 		i;
	
	if(rhs.size() == 0 || rhs[0] == Grammar::lambda) {
		result.insert(Grammar::lambda);
	} else {
		result = first_set[rhs[0]];
		for(i = 1; i < rhs.size() && 
			first_set[rhs[i-1]].find(Grammar::lambda) != first_set[rhs[i-1]].end(); i++) {
			set<string> f = first_set[rhs[i]];
			f.erase(Grammar::lambda);
			result.insert(f.begin(), f.end());	
		}
		if(i == rhs.size() 
			&& first_set[rhs[i-1]].find(Grammar::lambda) != first_set[rhs[i-1]].end()) {
			result.insert(Grammar::lambda);
		} else {
			result.erase(Grammar::lambda);
		}
	}
	
	return result;
} 
/*
 * please call get_predict_set() after fill_follow_set() and fill_first_set()
 */
set<string> Grammar::get_predict_set(Production p) {
	set<string> result;
	set<string> rfirst;
	
	rfirst = compute_first(p.RHS);
	if(rfirst.find(Grammar::lambda) != rfirst.end()) {
		rfirst.erase(Grammar::lambda);
		result.insert(rfirst.begin(), rfirst.end());
		rfirst = follow_set[p.LHS];
		result.insert(rfirst.begin(), rfirst.end());
	} else {
		result.insert(rfirst.begin(), rfirst.end());
	}
	
	return result;
}
/*
 * 
 */
void Grammar::fill_lltable() {
	string		A; // nonterminal
	Production 	p;
	
	for(size_t i = 0; i < rules.size(); i++) {
		p = rules[i];
		A = p.LHS;
		set<string> predict_set = get_predict_set(p);
		
		for(set<string>::iterator it = predict_set.begin();
			it != predict_set.end(); it++) {
			assert(lltable[A].find(*it) == lltable[A].end());
			lltable[A][*it] = p;
		}
	}
	
}
void Grammar::buildSymbols() {
	symbols.clear();
	for(size_t i = 0; i < rules.size(); i++) {
		symbols.insert(rules[i].LHS);
		for(size_t j = 0; j < rules[i].RHS.size(); j++) {
			symbols.insert(rules[i].RHS[j]);
		}
	}
}
bool Grammar::isNonterminal(string token) {
#ifdef HTMLProduction
	if(token == Grammar::lambda)
		return false;
	if(token[0] == '<' && token[token.length() - 1] == '>')
		return true;
	return false;
#else
	if(token == Grammar::lambda)
		return false;
	for(size_t i = 0; i < token.length(); i++) {
		if(isupper(token[i]))
			return true;
	}
	return false;
#endif
}
/* ------------------------
Grammar LL method
-------------------------- */
map<string, bool> Grammar::mark_lambda() {
	bool 				rhs_derives_lambda;
	bool 				changes;
	Production 			p;
	
	derives_lambda.clear();
	
	/* initially, nothing is marked. */
	for(size_t i = 0; i < rules.size(); i++) {
		derives_lambda[rules[i].LHS] = false;
	}
	do {
		changes = false;
		for(size_t i = 0; i < rules.size(); i++) {
			p = rules[i];
			if(!derives_lambda[p.LHS]) {
				if(p.RHS.size() == 0 || p.RHS[0] == Grammar::lambda) {
					changes = derives_lambda[p.LHS] = true;
					continue;
				}
				/* does each part of RHS derive lambda ? */
				rhs_derives_lambda = derives_lambda[string(p.RHS[0])];
				for(size_t j = 1; j < p.RHS.size(); j++) {
					rhs_derives_lambda &= derives_lambda[p.RHS[j]];
				}
				if(rhs_derives_lambda) {
					changes = true;
					derives_lambda[p.LHS] = true;
				}
			}
		}
	} while(changes);
	return derives_lambda;
}
void Grammar::fill_first_set() {
	
	string 		A; // nonterminal
	string 		a; // terminal
	Production 	p;
	bool 		changes;
		
	mark_lambda();
	first_set.clear();
	
	for(size_t i = 0; i < rules.size(); i++) {
		A = rules[i].LHS;
		if(derives_lambda[A])
			first_set[A].insert(Grammar::lambda);
	}
	
	for(size_t i = 0; i < rules.size(); i++) {
		for(size_t j = 0; j < rules[i].RHS.size(); j++) {
			a = rules[i].RHS[j];
			if(!isNonterminal(a)) {
				if(a != Grammar::lambda)
					first_set[a].insert(a);
				if(j == 0) { // A -> aXX
					first_set[rules[i].LHS].insert(a);
				}
			}
		}
	}
	
	do {
		changes = false;
		for(size_t i = 0; i < rules.size(); i++) {
			p = rules[i];
			set<string> rfirst = compute_first(p.RHS);
			size_t oldsize = first_set[p.LHS].size();
			first_set[p.LHS].insert(rfirst.begin(), rfirst.end());
			size_t newsize = first_set[p.LHS].size();
			if(oldsize != newsize)
				changes = true;
		}
	} while(changes);
} 
void Grammar::fill_follow_set() {
	string 	A, B; // nonterminal
	Production 	p;
	bool 	changes;
	
	for(size_t i = 0; i < rules.size(); i++) {
		A = rules[i].LHS;
		follow_set[A].clear();
	}
	
	follow_set[start_symbol].insert(Grammar::lambda);
		
	do {
		changes = false;
		for(size_t i = 0; i < rules.size(); i++) {
			/* A -> a B b
			 * I.e. for each production and each occurrence
			 * of a nonterminal in its right-hand side. 
			 */
			p = rules[i];
			A = p.LHS;
			for(size_t j = 0; j < p.RHS.size(); j++) {
				B = p.RHS[j];
				if(isNonterminal(B)) {
					vector<string> beta(p.RHS.begin() + j + 1, p.RHS.end());
					set<string> rfirst = compute_first(beta);
					size_t oldsize = follow_set[B].size();
					
					if(rfirst.find(Grammar::lambda) == rfirst.end()) {
						follow_set[B].insert(rfirst.begin(), rfirst.end());	
					} else {
						rfirst.erase(Grammar::lambda);
						follow_set[B].insert(rfirst.begin(), rfirst.end());	
						rfirst = follow_set[A];
						follow_set[B].insert(rfirst.begin(), rfirst.end());
					}
					size_t newsize = follow_set[B].size();			
					if(oldsize != newsize)
						changes = true;
				}
			}
		}
	} while(changes);
}
void Grammar::lldriver(queue<string> tokens) {
	stack<string> 	stk;
	string 			X;
	string			a;
	Production		p;
	/* Push the Start Symbol onto an empty stack */
	stk.push(start_symbol);
	
	while(!stk.empty() && !tokens.empty()) {
		X = stk.top();
		a = tokens.front();
		// cout << X << " " << a << endl;
		if(isNonterminal(X) && lltable[X].find(a) != lltable[X].end()) {
			p = lltable[X][a];
			stk.pop();
			for(int i = p.RHS.size() - 1; i >= 0; i--) {
				if(p.RHS[i] == Grammar::lambda)
					continue;
				stk.push(p.RHS[i]);
			}
		} else if(X == a) {
			stk.pop();
			tokens.pop();
		} else if(lltable[X].find(Grammar::lambda) != lltable[X].end()) {
			stk.pop();
		} else {
			/* Process syntax error. */
			puts("Bad!");
			return;
		}
	}
	while(!stk.empty()) {
		X = stk.top();
		if(lltable[X].find(Grammar::lambda) != lltable[X].end())
			stk.pop();
		else
			break;
	}
	if(tokens.size() == 0 && stk.size() == 0)
		puts("Good");
	else
		puts("Bad!");
	return;
}
/* ------------------------
Grammar LR method
-------------------------- */
void Grammar::build_action() {
	ConfigurationSet 	s;
	Production 			P;
	int					dotPos;
	set< pair<Production, ConfigurationSet::State> >::iterator it;
	
	for(size_t i = 0; i < LRstates.size(); i++) {
		s = LRstates[i];
		int reduce = 0, rule = 0, accept = 1;
		for(it = s.configs.begin(); it != s.configs.end(); it++) {
			P = it->first, dotPos = it->second.dot;
			if(dotPos == P.RHS.size())
				reduce++, rule = P.label;
			accept &= P.LHS == Grammar::start_symbol;
		}
		if(accept == 1)
			action_table[i] = 0;
		else if(reduce == 1)
			action_table[i] = -1;
		else
			action_table[i] = 1;
	}
#ifdef DEBUG
	printf("State |");
	for(size_t i = 0; i < LRstates.size(); i++)
		printf("%5d|", i);
	puts("");
	printf("Action|");
	for(size_t i = 0; i < action_table.size(); i++) {
		printf("%5d|", action_table[i]);
	}
	puts("");
#endif
}
void Grammar::build_CFSM() {
	set<ConfigurationSet> 	S;
	queue<ConfigurationSet>	Q;
	ConfigurationSet 		s0, sb;
	int 					label = 0;
	ConfigurationSet::State state;
	
	state.dot = 0;
	state.lookahead = vector<string>();
	state.lookahead.push_back(Grammar::lambda);
	for(size_t i = 0; i < rules.size(); i++) {
		if(rules[i].LHS == this->start_symbol) {
			s0.configs.insert(make_pair(rules[i], state));
		}
	}
	s0 = ConfigurationSet::closure0(s0, *this);
	s0.label = label++;
	
	S.insert(s0);
	Q.push(s0);
	
	buildSymbols();
	/* hw need */
	map<int, vector< pair<int, string> > > hwPrint;
	/* hw need */
	while(!Q.empty()) {
		s0 = Q.front(), Q.pop();
		LRstates.push_back(s0);
		for(set<string>::iterator it = symbols.begin();
			it != symbols.end(); it++) {
			sb = ConfigurationSet::go_to0(s0, *it, *this);
			if(sb.configs.size() > 0) {
				if(S.find(sb) == S.end()) {
					sb.label = label++;
					S.insert(sb);
					Q.push(sb);
				}
				
				go_to_table[s0.label][*it] = (* S.find(sb)).label;
				/* hw need */
				hwPrint[(* S.find(sb)).label].push_back(make_pair(s0.label, *it));
			}
		}
	}
	// build_action();
#ifdef DEBUG	
	printf("Total State: %d\n", label);
	for(int i = 0; i < label; i++) {
		if(hwPrint[i].size() > 0) {
			printf("State %d from", i);
			for(vector< pair<int, string> >::iterator it = hwPrint[i].begin();
				it != hwPrint[i].end(); it++) {
				printf("%cState %d(%s)", it == hwPrint[i].begin() ? ' ' : ',', it->first, it->second.c_str());
			}
			puts("");
		} else {
			printf("State %d\n", i);
		}
		LRstates[i].print(*this);
		puts("");
	}
#endif
}
int Grammar::slr1driver(queue<string> tokens) {
	stack<int> 		stateStk;
	stack<string> 	tokenStk;
	int 			state;
	string			X;
	
	stateStk.push(0); /* push start state */
	while(!tokens.empty()) {
		state = stateStk.top();
		X = tokens.front();
#ifdef DEBUG 
		puts("");
		printf("state %d front %s\n", state, X.c_str());
		LRstates[state].print(*this);
		for (std::stack<int> dump = stateStk; !dump.empty(); dump.pop())
        	std::cout << "state stack "<< dump.top() << '\n';
		for (std::stack<string> dump = tokenStk; !dump.empty(); dump.pop())
        	std::cout << "token stack "<< dump.top() << '\n';
#endif
		int reduce = 0, shift = 0;
		Production P;
		for(set< pair<Production, ConfigurationSet::State> >::iterator it = LRstates[state].configs.begin(); 
			it != LRstates[state].configs.end(); it++) {
			Production q = it->first;
			ConfigurationSet::State s = it->second;
			if(follow_set[q.LHS].find(X) != follow_set[q.LHS].end() && 
					(s.dot == q.RHS.size() || q.RHS[0] == Grammar::lambda)) {
				reduce++;
				P = q;
			}
		}
		if(go_to_table[state].find(X) != go_to_table[state].end())
			shift++;
		if(reduce + shift >= 2)
			assert(false); // grammar can't use simple LR.
		if(reduce + shift == 0)
			return 0;
		if(reduce == 1) { // Reduce
			for(size_t i = 0; i < P.RHS.size(); i++) 
				tokenStk.pop(), stateStk.pop();
			tokenStk.push(P.LHS);
			state = stateStk.top();
			if(go_to_table[state].find(P.LHS) == go_to_table[state].end()) {
				return 0;
			}
			state = go_to_table[state][P.LHS];
			stateStk.push(state);
		} else { // shift
			state = go_to_table[state][X];
			stateStk.push(state);
			tokenStk.push(X);
			tokens.pop();
		}
	}
	while(!stateStk.empty()) {
		state = stateStk.top();
		X = Grammar::lambda;
#ifdef DEBUG 
		puts("");
		printf("state %d front %s\n", state, X.c_str());
		LRstates[state].print(*this);
		for (std::stack<int> dump = stateStk; !dump.empty(); dump.pop())
        	std::cout << "state stack "<< dump.top() << '\n';
		for (std::stack<string> dump = tokenStk; !dump.empty(); dump.pop())
        	std::cout << "token stack "<< dump.top() << '\n';
#endif
		int reduce = 0, shift = 0;
		Production P;
		for(set< pair<Production, ConfigurationSet::State> >::iterator it = LRstates[state].configs.begin(); 
			it != LRstates[state].configs.end(); it++) {
			Production q = it->first;
			ConfigurationSet::State s = it->second;
			if(follow_set[q.LHS].find(X) != follow_set[q.LHS].end() && 
					(s.dot == q.RHS.size() || q.RHS[0] == Grammar::lambda)) {
				reduce++;
				P = q;
			}
		}
		if(go_to_table[state].find(X) != go_to_table[state].end())
			shift++;
		if(reduce + shift >= 2)
			assert(false); // grammar can't use simple LR.
		if(reduce + shift == 0)
			return 0;
		if(reduce == 1) { // Reduce
			for(size_t i = 0; i < P.RHS.size(); i++) 
				tokenStk.pop(), stateStk.pop();
			tokenStk.push(P.LHS);
			state = stateStk.top();
			if(go_to_table[state].find(P.LHS) == go_to_table[state].end()) {
				if(P.LHS == Grammar::start_symbol)
					return 1;
				return 0;
			}
			state = go_to_table[state][P.LHS];
			stateStk.push(state);
		} else { // shift
			state = go_to_table[state][X];
			stateStk.push(state);
			tokenStk.push(X);
			tokens.pop();
		}
	}
	return 0;
}
void parsingProduction(string r, Grammar &g) {
	static int 		production_label = 0;
	stringstream 	sin(r);
	string 			lhs, foo;
	vector<string> 	tokens;
	sin >> lhs >> foo;
	while(sin >> foo)
		tokens.push_back(foo);
	Production p(lhs, tokens);
	p.label = ++production_label;
	g.rules.push_back(p);
}
bool isNumber(string str) {
	for(int i = 0; i < str.length(); i++) {
		if(!isdigit(str[i]))
			return false;
	}
	return true;
}
int scanTokens(char s[], queue<string>& tokens, vector<string>& val) {
	string keyword[18] = {"AND", "THEN", "GO", "KEEP", 
			"RIGHT", "LEFT", "FIRST", "SECOND", "THIRD", 
			"AT", "RECORD", "TIME", "TO", "KMH", "CHANGE",
			"AVERAGE", "SPEED", "CAS"};
	for(int i = 0; s[i]; i++) {
		if(s[i] == '"') {
			// s-word can't empty, and after the opening speech marks no more space.
			if(s[i + 1] == '"' || isspace(s[i + 1]))	
				return 0;
			i++;
			while(s[i] != '"') {
				if(isupper(s[i])) {}
				else if(isspace(s[i])) {s[i] = '_';}
				else if(s[i] == '.') {
					if(isspace(s[i - 1]) || s[i - 1] == '_') {
						return 0;
					}
				} else {
					return 0;
				}
				i++;
			}
			if(s[i] == '\0' || isspace(s[i - 1]) || s[i - 1] == '_')
				return 0;
		}
	}
	stringstream 	sin(s);
	string 			token;
	while(sin >> token) {
		int f = 0;
		for(int i = 0; i < 18; i++) {
			if(token == keyword[i])
				tokens.push(token), val.push_back(token), f = 1;
		}
		if(f)	continue;
		if(token[0] == '"')
			tokens.push("SIGNWORDS"), val.push_back(token), f = 1;
		if(f)	continue;
		if(isNumber(token))
			tokens.push("NNN"), val.push_back(token), f = 1;
		if(f)	continue;
		return 0;
	}
	return 1;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout);
	Grammar g;
	parsingProduction("<instruction> 	-> <navigational>", g);
	parsingProduction("<instruction> 	-> <time-keeping>", g);
	parsingProduction("<instruction> 	-> <navigational> AND <time-keeping>", g);
	parsingProduction("<navigational> 	-> <directional>", g);
	parsingProduction("<navigational> 	-> <navigational> AND THEN <directional>", g);
	parsingProduction("<directional> 	-> <how> <direction>", g);
	parsingProduction("<directional> 	-> <how> <direction> <where>", g);
	parsingProduction("<how> 			-> GO", g);
	parsingProduction("<how> 			-> GO <when>", g);
	parsingProduction("<how>			-> KEEP", g);
	parsingProduction("<direction> 		-> RIGHT", g);
	parsingProduction("<direction>		-> LEFT", g);
	parsingProduction("<when>			-> FIRST", g);
	parsingProduction("<when>			-> SECOND", g);
	parsingProduction("<when>			-> THIRD", g);
	parsingProduction("<where> 			-> AT <sign>", g);
	parsingProduction("<sign>			-> SIGNWORDS", g);
	parsingProduction("<time-keeping> 	-> <record>", g);
	parsingProduction("<time-keeping>	-> <change>", g);
	parsingProduction("<record>			-> RECORD TIME", g);
	parsingProduction("<change>			-> <cas> TO NNN KMH", g);
	parsingProduction("<cas>			-> CHANGE AVERAGE SPEED", g);
	parsingProduction("<cas> 			-> CAS", g);
	g.start_symbol = "<instruction>";
		
	g.fill_first_set();
	g.fill_follow_set();
	g.build_CFSM();
	
	char 	line[1024];
	int 	cases = 0;
	while(gets(line)) {
		if(!strcmp(line, "#"))
			break;
		queue<string> tokens;
		vector<string> val;
		int f = scanTokens(line, tokens, val);
		printf("%3d.", ++cases);
		if(!f) {
			puts(" Trap!");
			continue;
		}
		f = g.slr1driver(tokens);
		if(!f) {
			puts(" Trap!");
			continue;
		}
		for(int i = 0; i < val.size(); i++) {
			if(val[i][0] == '"')
				for(int j = 0; j < val[i].length(); j++)
					if(val[i][j] == '_')
						val[i][j] = ' ';
			printf(" %s", val[i].c_str());
		}
		puts("");
	}
	return 0;
}

Read More +

Jun 19 2014

解題區►解題區 - UVa

UVa 345 - It's Ir-Resist-Able

Problem

A common component in electronic circuits is the resistor. Each resistor has two terminals, and when current flows through a resistor, some of it is converted to heat, thus ``resisting”; the flow of the current. The extent to which it does this is indicated by a single positive numeric value, cleverly called the resistance of the resistor. By the way, the units of resistance are Ohms. Here’s what a single resistor looks like in a diagram of an electronic circuit:

When two resistors are connected in series, as shown below, then their equivalent resistance is just the sum of the resistances of the individual resistors. For example, if the two resistors below had resistances of 100 and 200 Ohms, respectively, then the combined resistance (from point A to point B) would be 300 Ohms. Of course, combining three or more resistors in series would yield a resistance equal to sum of all the individual resistances.

Resistors may also be connected in parallel, like this:

If these two resistors had resistances of 100 and 150 Ohms, then the parallel combination would yield an equivalent resistance between points A and B of

displaymath61

Connecting three resistors in parallel uses the same rule, so a 100 Ohm, 150 Ohm, and 300 Ohm resistor in parallel would yield a combined resistance of just 50 Ohms: that is,

displaymath63

In this problem you’re provided one or more descriptions of resistors and their interconnections. Each possible interconnection point (the terminals of a resistor) is identified by a unique positive integer, its label. And each resistor is specified by giving its two interconnection point labels and its resistance (as a real number).

For example, the input

1 2 100

would tell us that a 100 Ohm resistor was connected between points 1 and 2. A pair of resistors connected in series might be specified like this:

1 2 100
2 3 200

Here we’ve got our 100 Ohm resistor connected at points 1 and 2, and another 200 Ohm resistor connected to points 2 and 3. Two resistors in parallel would be similarly specified:

1 2 100
1 2 150

Once you know how the resistors are interconnected, and the resistance of each resistor, it’s possible to determine the equivalent resistance between any two points using the simple rules given above. In some cases, that is. Some interconnections of resistors can’t be solved using this approach: you won’t encounter any of these in this problem, however.

Notes

Be aware that there may be input test cases with some resistors that don’t contribute to the overall resistance between the indicated points. For example, in the last case shown in the Sample Input section below, the resistor between points 1 and 2 is unused. There must be some flow through a resistor if it is to contribute to the overall resistance.
No resistor will have its ends connected together. That is, the labels associated with the ends of a resistor will always be distinct.

Input

There will be one or more cases to consider. Each will begin with a line containing three integers N, A, and B. A and B indicate the labels of points between which you are to determine the equivalent resistance. N is the number of individual resistors, and will be no larger than 30. N, A and B will all be zero in the line following the last case. Following each N A B line will be N lines, each specifying the labels of the points where a resistor is connected, and the resistance of that resistor, given as a real number.

Output

For each input case, display a line that includes the case number (they are numbered sequentially starting with 1) and the equivalent resistance, accurate to two decimal places.

Sample Input

Sample Output

1
2
3

Case 1: 300.00 Ohms
Case 2: 60.00 Ohms
Case 3: 75.00 Ohms

Solution

題目描述：

給定指定的兩個端點 A B，接著會有 N 個電阻，每個電阻值位於端點 X Y 之間。
求 A B 之間的等效電阻，特別注意到端點編號是任意整數，並且有可能兩個端點相同 (A = B)，也有可能會有無會流經的電路區域。

題目解法：

我們假設每個端點的電動勢 (Volt)，使用克希荷夫電路定律（Kirchhoff Circuit Laws）中的 電流定律 ，得到下列公式。

對於每一個端點而言，入電流總量等於出電流總量：

$$\sum_{j = 1}^{n} \frac{V_{j} - V_{i}}{R_{i, j}} = 0$$

但是題目給定的起點和終點並不會在其中，因此假設起點 V[A] = INF，終點 V[B] = 0，接著算出其他所有點的電動勢。共有 n - 2 條方程式，n - 2 個變數，使用高斯消去求解。

必須預處理與起點、終點之間的電流關係。
特別注意到起點和終點相同，直接輸出等效電阻 0。
端點編號離散化集中處理。

#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <vector>
#include <math.h>
#include <map>
#include <iostream>
using namespace std;
// learn: http://blog.csdn.net/jiangshibiao/article/details/28661223		
#define MAXN 105
#define INF 1e+6
#define eps 1e-9
double R[MAXN][MAXN] = {}, V[MAXN] = {}; // R: resist, V: voltage
double f[MAXN][MAXN] = {}; // function need solved;
int main() {
	int N, A, B;
	int x, y, l;
	int cases = 0;
	double w;
	char s1[105], s2[105];
	while(scanf("%d %d %d", &N, &A, &B) == 3) {
		if(N == 0)
			break;
		map<int, int> label;
		l = label[A];
		if(l == 0)	label[A] = label.size();
		A = label[A];
		
		l = label[B];
		if(l == 0)	label[B] = label.size();
		B = label[B];
		
		memset(R, 0, sizeof(R));
		memset(V, 0, sizeof(V));
		memset(f, 0, sizeof(f));
		vector<double> g[MAXN][MAXN];
		for(int i = 0; i < N; i++) {
			scanf("%d %d %lf", &x, &y, &w);
			
			l = label[x];
			if(l == 0)	label[x] = label.size();
			x = label[x];
			
			l = label[y];
			if(l == 0)	label[y] = label.size();
			y = label[y];
			
			g[x][y].push_back(w);
			g[y][x].push_back(w);
		}
		N = label.size();
		for(int i = 1; i <= N; i++) {
			for(int j = 1; j <= N; j++) {
				if(g[i][j].size()) {
					double r = 0;
					for(int k = 0; k < g[i][j].size(); k++) {
						r += 1.0 / g[i][j][k];
					}
					R[i][j] = 1.0 / r;
				}
			}
		}
		V[A] = INF, V[B] = 0;
		for(int i = 1; i <= N; i++) {
			if(i == A)	continue;
			if(i == B)	continue;
			if(R[i][A] > 0)
				f[i][i] -= 1.0 / R[i][A], f[i][N + 1] -= V[A] / R[i][A];
			if(R[i][B] > 0)
				f[i][i] -= 1.0 / R[i][B], f[i][N + 1] -= V[B] / R[i][B];
			for(int j = 1; j <= N; j++) {
				if(R[i][j] > 0 && i != j && j != A && j != B)
					f[i][j] = 1.0 / R[i][j], f[i][i] -= 1.0 / R[i][j];
			}
		}
		// Gaussian Elimination
		for(int i = 1; i <= N; i++) {
			int k = i;
			for(int j = i + 1; j <= N; j++)
				if(f[j][i] > 0)
					k = j;
			if(fabs(f[k][i]) < eps)
				continue;
			for(int j = 1; j <= N + 1; j++)
				swap(f[i][j], f[k][j]);
			for(int j = 1; j <= N; j++) {
				if(i == j)	continue;
				for(int k = N + 1; k >= i; k--)
					f[j][k] = f[j][k] - f[j][i] / f[i][i] * f[i][k];
			}
		}
		for(int i = 1; i <= N; i++) {
			if(i == A)	continue;
			if(i == B)	continue;
			if(fabs(f[i][i]) > eps)
				V[i] = f[i][N + 1] / f[i][i];
		}
		
		double IB = 0;
		for(int i = 1; i <= N; i++)
			if(R[i][B] > 0)
				IB += V[i] / R[i][B];
		if(fabs(IB) < eps)
			printf("Case %d: %.2lf Ohms\n", ++cases, 0);
		else
			printf("Case %d: %.2lf Ohms\n", ++cases, (V[A] - V[B]) / IB);
	}
	return 0;
}

Read More +

Jun 17 2014

解題區►解題區 - UVa

UVa 313 - Intervals

Problem

In the ceiling in the basement of a newly open developers building a light source has been installed. Unfortunately, the material used to cover the floor is very sensitive to light. It turned out that its expected life time is decreasing dramatically. To avoid this, authorities have decided to protect light sensitive areas from strong light by covering them. The solution was not very easy because, as it is common, in the basement there are different pipelines under the ceiling and the authorities want to install the covers just on those parts of the floor that are not shielded from the light by pipes. To cope with the situation, the first decision was to simplify the real situation and, instead of solving the problem in 3D space, to construct a 2D model first.

Within this model, the x-axis has been aligned with the level of the floor. The light is considered to be a point light source with integer co-ordinates tex2html_wrap_inline36 . The pipes are represented by circles. The center of the circle i has the integer co-ordinates tex2html_wrap_inline40 and an integer radius tex2html_wrap_inline42 . As pipes are made from solid material, circles cannot overlap. Pipes cannot reflect the light and the light cannot go through the pipes. You have to write a program which will determine the non-overlapping intervals on the x-axis where there is, due to the pipes, no light from the light source.

Input

The input file consists of blocks of lines, each of which except the last describes one situation in the basement. The first line of each block contains a positive integer number N < 500 expressing the number of pipes. The second line of the block contains two integers tex2html_wrap_inline48 and tex2html_wrap_inline50 separated by one space. Each of the next N lines of the block contains integers tex2html_wrap_inline54 , tex2html_wrap_inline56 and tex2html_wrap_inline42 , where tex2html_wrap_inline60 . Integers in individual lines are separated by one space. The last block consists of one line containing n = 0.

Output

The output file consists of blocks of lines, corresponding to the blocks in the file (except the last one). One empty line must be put after each block in the output file. Each of the individual lines of the blocks in the output file will contain two real numbers, the endpoints of the interval where there is no light from the given point light source. The reals are exact to two decimal places and separated by one space. The intervals are sorted according to increasing x-coordinate.

Sample Input

6
300 450
70 50 30
120 20 20
270 40 10
250 85 20
220 30 30
380 100 100
1
300 300
300 150 90
1
300 300
390 150 90
0

Sample Output

0.72 78.86
88.50 133.94
181.04 549.93
75.00 525.00
300.00 862.50

Solution

題目描述：

現在天花板上面有一盞燈，然後下方有數個圓，請問陰影部分的區間由小至大輸出分別為何。
假設不會有圓的高度大於燈的位置，而陰影呈現在 x 軸上。

題目解法：

求圓 (cx, cy, r) 外一點的切線，由於點 (a, b) 在圓外，通常此點切於圓的線會有兩條。

假設該線斜率為 m，則通過的線為 y = m * (x - a) + b。

藉由點線距公式 |m * (cx - a) - cy + b |/sqrt(m*m + 1) = r，求得 m 之後得到兩條切線，往後求交 x 軸的位置即可。(特別考慮 m 不存在的情況)

最後使用掃描線算法來算聯集。

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
int main() {
    int N;
    double bx, by, cx, cy, cr;
    while (scanf("%d", &N) == 1 && N) {
    	scanf("%lf %lf", &bx, &by);
        vector< pair<double, double> > interval;
        for (int i = 0; i < N; i++) {
            scanf("%lf %lf %lf", &cx, &cy, &cr);
            double a, b, c;
            a = (cx - bx) * (cx - bx) - cr * cr;
            b = 2 * (cx - bx) * (by - cy);
            c = (by - cy) * (by - cy) - cr * cr;
            if (b * b - 4 * a * c > 0) {
#define eps 1e-6
                if (fabs(a) > eps) {
                    double m1 = (-b + sqrt(b * b - 4 * a * c))/(2 * a);
                    double m2 = (-b - sqrt(b * b - 4 * a * c))/(2 * a);
                    double l, r;
                    c = by - m1 * bx;
                    l = -c / m1;
                    c = by - m2 * bx;
                    r = -c / m2;
                    if (l >= r)
                        swap(l, r);
                    interval.push_back(make_pair(l, r));
                } else {
                    double m1 = -c / b;
                    double l, r;
                    c = by - m1 * bx;
                    l = -c / m1;
                    r = bx;
                    if (l >= r)
                        swap(l, r);
                    interval.push_back(make_pair(l, r));
                }
            }
        }
        sort(interval.begin(), interval.end());
        double coverL, coverR;
        coverL = interval[0].first;
        coverR = interval[0].second;
        for (int i = 0; i < interval.size(); i++) {
            if (interval[i].first <= coverR) {
                coverR = max(coverR, interval[i].second);
            } else {
                printf("%.2lf %.2lf\n", coverL, coverR);
                coverL = interval[i].first;
                coverR = interval[i].second;
            }
        }
        printf("%.2lf %.2lf\n", coverL, coverR);
        puts("");
    }
    return 0;
}

Read More +