采采的生活隨筆: 9月 2015

2015年9月30日星期三

Uva 10371 Time Zones

題目來源：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1312

題意：

題目開頭先給你時區的簡稱，Input ：time 時區1 時區2

Output：將在時區1的time 換算成在時區2的time 並輸出

胡言亂語：

這題，卡在12小時制時間的換算超久QAQ

而函式的用法和#uva 860差不多XD

可以點進去看就好，先附上debug兩天...的程式碼~~~

...最後竟然是我把720打成780....

	#include<iostream>
	#include<cstring>
	#include<cstdio>
	#include<cstdlib>
	#include<iomanip>
	#include<map>
	using namespace std;

	map <string,double> table;

	void init(){
	table["UTC"] = 0 , table["GMT"] = 0;
	table["BST"] = 1 , table["IST"] = 1;
	table["WET"] = 0 , table["WEST"] = 1;
	table["CET"] = 1 , table["CEST"] = 2;
	table["EET"] = 2 , table["EEST"] = 3;
	table["MSK"] = 3 , table["MSD"] = 4;
	table["AST"] = -4 , table["ADT"] = -3;
	table["NST"] = -3.5 , table["NDT"] = -2.5;
	table["EST"] = -5, table["EDT"] = -4;
	table["CST"] = -6, table["CDT"] = -5;
	table["MST"] = -7, table["MDT"] = -6;
	table["PST"] = -8, table["PDT"] = -7;
	table["HST"] = -10, table["AKST"] = -9;
	table["AKDT"] = -8 , table["AEST"] = 10;
	table["AEDT"] = 11 , table["ACST"] = 9.5;
	table["ACDT"] = 10.5 , table["AWST"] = 8;
	}


	int main(){
	init();//建表

	int N,time,short_hand,long_hand;//時針、分針
	string st,local,outside;//a.m/p.m、當地時間、外地時間
	int tag;



	scanf("%d",&N);//讀入有幾筆測資
	cin.get();//讀掉換行字元
	while(N--){
	tag = 0;
	char *p, str1[100] ;
	cin.getline(str1,100);
	p = strtok(str1, " :");
	while (p != NULL) {
	tag++;
	if(tag==1){
	if(isdigit(*p)) short_hand = atof(p);
	else {
	tag = 3;
	if(!strcmp(p,"noon")) time = 12*60;
	if(!strcmp(p,"midnight")) time = 0;
	}
	}
	else if(tag==2) long_hand = atof(p);
	else if(tag==3) {
	time = long_hand+ short_hand*60;
	if(time>=720&&time<780) time-=720;
	if(!strcmp(p,"p.m.")) {
	time+=720;
	}

	}
	else if(tag==4) local = p;
	else if(tag==5) outside = p;
	p = strtok(NULL, " :");
	}

	time =time+ (table[outside]-table[local])60+2460;

	time %=1440;//因為time可能為負
	short_hand = (time/60)%24;
	long_hand = time%60;
	//printf("%d ",time);
	if(time == 0)
	printf("midnight\n");
	else if(time == 720)
	printf("noon\n");
	else{
	cout<<(time/60%12?time/60%12:12)<<":"<<setw(2)<<setfill('0')<<(time%60)<<" ";
	cout<<(time>720?"p.m.":"a.m.")<<endl;

	}


	}

	}

view raw tet.cpp hosted with ❤ by GitHub

Uva 860 Entropy Text Analyzer

題目來源：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=801

題意：

這題在luckycat沒有翻譯..有點難過，畢竟英文真的沒有很好。

first,他會先輸入一篇文章，你要按照公式，分別輸出他的單字總數、ET、Erel。

胡言亂語：

//記得當時我問同學題意時，它們都說：你帶公式就好啦，但我就是不懂公式的意思咩=3=

作法講起來真的蠻簡單的

首先你要會將句子中的單字擷取出來，所以會用到strtok( )這個函式，他的用法是：

	//開始分解str1,遇到, .:;!?()\"這些符號則分割成P
	p = strtok(str1, ", .:;!?()\"");
	while (p != NULL) {
	cout<<p<<endl;//輸出p

	//從剛剛還沒切玩的地方繼續切
	p = strtok(NULL, ", .:;!?()\"");
	}

view raw tet.cpp hosted with ❤ by GitHub

這樣就可以將單字取出來了！

//但要注意str1是 char[]喔~是cstring (char string)才可以使用=)

//比較兩個cstring是否相同可以使用strcmp(str1,str2)，相同回傳0，不同回傳非零數字~

取出來後就可以順便計算其出現頻率。因此就用到map了！

剛認識map時，覺得他的感覺很像hash(雜湊)，你的key會對應到一個抽屜，你可以在抽屜內放數字進去。因此在這邊，我們把剛剛取出的單字p當成key，把它出現頻率放到對應的抽屜裡：

	#include<map>
	using namespace std;

	map <string,int> tree;//key是string 抽屜裡放的是int
	map <string,int>::iterator it;

	//用法：
	p = strtok(str1, ", .:;!?()\"");
	while (p != NULL) {
	con++;
	if(p[0]<97) p[0]+=32;//單字要全小寫
	words=p;//將char[]->string
	it = tree.find(words);//尋找key對應到的抽屜
	if(it==tree.end()) tree[words] = 1;//沒找到
	else tree[words]++;//找到，代表前面有出現過
	p = strtok(NULL, ", .:;!?()\"");
	}

view raw tet.cpp hosted with ❤ by GitHub

最後再將答案計算並輸出就好 ^_____^

//n表示有幾種單字，爛瘩表示總共有幾個單字。

程式碼：

	#include<cstdio>
	#include<iostream>
	#include<cstring>
	#include<map>
	#include<cmath>
	using namespace std;

	map <string,int> tree;
	map <string,int>::iterator it;

	//計算並輸出
	void printf_out(int con){
	double ET = 0;
	for(it = tree.begin();it!=tree.end();it++)
	ET += it->second*(log10(con)-log10(it->second));

	ET/=con;
	printf("%d %.1lf %.0lf\n",con,ET,(ET/log10(con))*100);

	}

	int main(){
	string words;
	int con = 0;//計算總共有己的單字
	char *p, str1[100005] ;
	tree.clear();//清空map
	while(cin.getline(str1,100005)){
	if(!strcmp(str1,"**END_OF_INPUT**"))
	break;
	if(!strcmp(str1,"**END_OF_TEXT**")){
	printf_out(con);
	tree.clear();
	con = 0;
	}

	else{
	p = strtok(str1, ", .:;!?()\"");
	while (p != NULL) {
	con++;
	if(p[0]<97) p[0]+=32;
	words=p;
	it = tree.find(words);
	if(it==tree.end()) tree[words] = 1;//沒找到
	else tree[words]++;
	p = strtok(NULL, ", .:;!?()\"");
	}
	}
	}
	}

view raw tet.cpp hosted with ❤ by GitHub

2015年9月23日星期三

UVa10221 Satellites

題目來源：https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1162

胡言亂語：

找弧長和弦長的公式找好久喔 ... 再次要在code book加上新東西了XD

這題我犯的錯誤是，忘記輸出小數點後6位，輸出小數的話用printf 比較好寫

double x;

printf("%.nlf",x);

這樣就可以輸出小數點後n位了。=)

程式碼：

	#include<iostream>
	#include<cmath>
	#include<cstdio>
	using namespace std;
	int main(){
	double s,a;
	string str;
	while(cin>>s>>a>>str){
	if(str[0]=='m') a/=60;
	if(a>180) a=360-a;
	s+=6440;
	printf("%.6lf %.6lf\n",aacos(-1.0)/180.0s,2.0ssin(a*acos(-1.0)/180.0/2.0));

	}
	}

view raw 001.cpp hosted with ❤ by GitHub

Uva 478 Points in Figures: Rectangles, Circles, Triangles

題目來源：https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=419

胡言亂語：

這題原本我亂看題目，所以有重寫一次...

題目要求輸出一圖形順序，我以為先輸出完矩形、在圓形、在三角形...

因此思考了一下，要怎麼樣存圖形比較方便。分別設三個array存不一樣的圖形是笨方法。最後：

struct Point{

double x,y;

};

struct graph{

char ch; //判斷是什麼圖形

Point a,b,c;

double radius;

}P[11];

多設的變數可以不用理他，像是圓形就只需用到Point a，b,c根本用不到，但沒關係

這樣只要從P[1]~P[i]比較是否在圖形內就好

程式碼：

	#include<iostream>
	#include<cstdio>
	#include<cstdlib>
	#include<cmath>
	using namespace std;
	int sum;//計算測試點數量
	bool tag;//標記是否已有在圖形內

	//存點
	struct Point{
	double x,y;
	};

	//存圖形
	struct graph{
	char ch;
	Point a,b,c;
	double radius;
	}P[11];

	//計算三角形面積
	double get_area(Point a, Point b, Point c) {
	return fabs(0.5 * ((c.y-a.y)(b.x-a.x) - (b.y-a.y)(c.x-a.x)));
	}

	//判斷是否為矩形內
	void Test_rectangles(Point t,int i){
	if(t.x>P[i].a.x&&t.x<P[i].b.x&&t.y<P[i].a.y&&t.y>P[i].b.y){
	printf("Point %d is contained in figure %d\n",sum,i);
	tag=false;
	}
	}

	//判斷是否為圓形內
	void Test_circles(Point t,int i){
	if(sqrt((t.x-P[i].a.x)(t.x-P[i].a.x)+(t.y-P[i].a.y)(t.y-P[i].a.y))-P[i].radius<0.00001){
	printf("Point %d is contained in figure %d\n",sum,i);
	tag=false;
	}
	}

	//判斷是否在三角形內
	void Test_triangles(Point t,int i){
	if(get_area(t,P[i].b,P[i].c)+get_area(P[i].a,t,P[i].c)+get_area(P[i].a,P[i].b,t)
	-get_area(P[i].a,P[i].b,P[i].c)<0.00001){
	printf("Point %d is contained in figure %d\n",sum,i);
	tag=false;
	}
	}

	int main(){
	char ch1;//讀數圖形的圖案
	sum = 0;//計算點數量
	int m=0;//計算圖形數量
	while(cin>>ch1){
	m++;
	P[m].ch = ch1;
	if(ch1=='*') break;
	switch(ch1){
	case 'r':{
	cin>>P[m].a.x>>P[m].a.y>>P[m].b.x>>P[m].b.y;
	break;
	}
	case 'c':{
	cin>>P[m].a.x>>P[m].a.y>>P[m].radius;
	break;
	}
	case 't':{
	cin>>P[m].a.x>>P[m].a.y>>P[m].b.x>>P[m].b.y>>P[m].c.x>>P[m].c.y;
	break;
	}
	}
	}

	Point point;
	while(cin>>point.x>>point.y){
	tag=true;
	sum++;//計算測試點數量
	if(point.x==9999.9&&point.y==9999.9) break;

	for(int i=1;i<=m;i++){
	switch(P[i].ch){
	case 't':{
	Test_triangles(point,i);
	break;
	}
	case 'c':{
	Test_circles(point,i);
	break;
	}
	case 'r':{
	Test_rectangles(point,i);
	break;
	}
	}
	}

	if(tag)
	printf("Point %d is not contained in any figure\n",sum);
	}
	}

view raw uva_191.cpp hosted with ❤ by GitHub

Uva 191 Intersection

題目來源：https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=127

胡言亂語：

剛看到這一題的時候，就想說，可能先要判斷線段和矩形的四個邊有沒有交點，在來判斷線段是否在矩形內，但想一想，會不會更簡單啊？？

突然想到，那把線段切成很多小點，判斷每個點是否在矩形內不就好了？

線段方程式：ax+by = c ==>千萬不要用這個，因為這樣就會有三個變數

y = ax+b ==>這樣只剩兩個變數而已

因此我已x為變化基準，計算x' = x+0.5為間距的點是否在矩形內，但這樣WA了。

測了一下，發現兩個錯誤

(1) 若為垂直線則無斜率，需要另外處理

(2) x' = x+0.1 之前間距(0.5)太大，會有漏掉的點

修改後終於AC了 ^___^

程式碼：

	#include<iostream>
	#include<algorithm>
	#include<cstdio>
	#include<cstdlib>
	using namespace std;

	struct Point {
	double x,y;
	};

	Point p1,p2;//設定矩形的左下和右下

	double a,b;//存入線段方程式的係數

	//判斷是否為矩形內
	//float不可能完全相同，有一定的誤差在
	bool Test_rectangles(Point t){
	if(t.x>p1.x-0.00001 && t.x<p2.x+0.00001 && t.y<p2.y+0.00001 && t.y>p1.y-0.0001)
	return true;
	else return false;
	}

	//計算線段的方程式
	void get_polynominal(Point m,Point n){
	a = (m.y-n.y)/(m.x-n.x);
	b = m.y-(a*m.x);
	}


	int main(){
	int N;
	bool tag;
	double u;
	scanf("%d",&N);
	Point line_point1,linr_point2,temp;
	while(N--){
	tag = false;
	scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&line_point1.x,&line_point1.y,&linr_point2.x,&linr_point2.y,&p1.x,&p1.y,&p2.x,&p2.y);
	//p1代表左下 p2代表右上
	if(p1.x>p2.x) swap(p1.x,p2.x);
	if(p1.y>p2.y) swap(p1.y,p2.y);

	//若為垂直線的情況，因為垂直線無斜率
	if(line_point1.x==linr_point2.x){
	if(line_point1.y>linr_point2.y) swap(line_point1.y,linr_point2.y);
	for(double i=line_point1.y;i<=linr_point2.y+0.0001;i+=0.003){
	temp.x = line_point1.x;
	temp.y = i;
	if(Test_rectangles(temp)){
	tag = true;
	printf("T\n");
	break;
	}
	}
	if(!tag) printf("F\n");
	continue;
	}

	//非垂直線情況
	if(line_point1.x> linr_point2.x) {
	temp = line_point1 ;
	line_point1 = linr_point2;
	linr_point2 = temp;
	}

	//取得斜率和係數 y=ax+b
	get_polynominal(line_point1,linr_point2);

	//注意：抓的點的密度要夠，不然會有誤差
	for(double i=line_point1.x;i<=linr_point2.x+0.0001;i+=0.05){
	temp.x = i;
	temp.y = a*i+b;
	if(Test_rectangles(temp)){
	tag = true;
	printf("T\n");
	break;
	}
	}

	if(!tag) printf("F\n");
	}
	}

view raw uva_191.cpp hosted with ❤ by GitHub

訂閱：文章 (Atom)

2015年9月30日 星期三

Uva 10371 Time Zones

Uva 860 Entropy Text Analyzer

2015年9月23日 星期三

UVa10221 Satellites

Uva 478 Points in Figures: Rectangles, Circles, Triangles

Uva 191 Intersection

2015年9月30日星期三

2015年9月23日星期三