May 19 2015

UVa 1438 - Asteroids

Problem

兩個行星碰撞，請問質量中心能夠距離最近為何。

兩個行星會呈現凸多面體的形式，給予行星多面體上的頂點。

Sample Input

Sample Output

0.75

Solution

題目雖然已經給定所有在凸面體上的頂點，應該是要做一次三維凸包。

質心之間能多近，就是兩質心連線的最短距離，連線後不保證線上每一點都在其中一個凸多面體內部。因此找到凸面體的質心後，窮舉每一個表面拉出的平面，求點到面的最短距離。兩個答案相加即可。

複習下三維凸包算法，維護 conflict graph 去玩的那個，參照網路上的模板繞過一圈，代碼還真是相當簡潔有力 (雖然時間跟空間使用上都沒有辦法好計算，基於期望值 …)！利用空間共平面的順逆時針，來維護外部點判定，解決了之前上課中的困擾。

#include <stdio.h> 
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
const double eps = 1e-8;
const int MAXN = 1024;
int cmpZero(double x) {
	if (fabs(x) < eps)	return 0;
	return x < 0 ? -1 : 1;
}
class ConvexHull3D {
public:
	struct Point3D {
		double x, y, z;
		Point3D(double a = 0, double b = 0, double c = 0):
			x(a), y(b), z(c) {}
		Point3D operator+(const Point3D &a) const {
			return Point3D(x + a.x, y + a.y, z + a.z);
		}
		Point3D operator-(const Point3D &a) const {
			return Point3D(x - a.x, y - a.y, z - a.z);
		}
		Point3D operator/(double a) const {
			return Point3D(x/a, y/a, z/a);
		}
		Point3D operator*(double a) const {
			return Point3D(x*a, y*a, z*a);
		}
		bool operator!=(const Point3D &a) const {
			return cmpZero(x - a.x) || cmpZero(y - a.y) || cmpZero(z - a.z);
		}
		Point3D cross(const Point3D &a) const { // outer product
			return Point3D(y*a.z - z*a.y, z*a.x - x*a.z, x*a.y - y*a.x);
		}
		double dot(const Point3D &a) const {
			return x*a.x + y*a.y + z*a.z;
		}
		double length() {
			return sqrt(x*x+y*y+z*z);
		}
		void read() {
			scanf("%lf %lf %lf", &x, &y, &z);
		}
	};
	struct Face {
		int a, b, c; 	// point3d id
		bool flag; 		// on Convex Hull
	};
	
	int n, tri_num;
	Point3D pt[MAXN];
	Face faces[MAXN*8];
	Face* g[MAXN][MAXN];
	
	double tri_area(Point3D a, Point3D b, Point3D c) { 	// value >= 0
		return ((a - c).cross(b - c)).length()/2;
	}
	double volume(Point3D a, Point3D b, Point3D c, Point3D d) { // directed
		return ((b - a).cross(c - a)).dot(d - a)/6;
	}
	double pt2Face(Point3D a, Point3D b, Point3D c, Point3D p) {
		Point3D n = (b - a).cross(c - a);
		Point3D t = p - a;
		double v = n.dot(t) / n.length();
		return fabs(v);
	}
	double ptWithFace(Point3D &p, Face &f) { // 0: p in f, <0, >0: above or below
		Point3D a, b, c;
		a = pt[f.b] - pt[f.a];
		b = pt[f.c] - pt[f.a];
		c = p - pt[f.a];
		return (a.cross(b)).dot(c);
	}
	bool samePlane(Face &s, Face &t) {
		Point3D a, b, c;
		bool ret = true;
		a = pt[s.a], b = pt[s.b], c = pt[s.c];
		ret = cmpZero(volume(a, b, c, pt[t.a])) == 0 &&
				cmpZero(volume(a, b, c, pt[t.b])) == 0 &&
				cmpZero(volume(a, b, c, pt[t.c])) == 0;
		return ret;
	}
	void deal(int a, int b, int p) {
		Face *f = g[a][b];
		if (f->flag) {
			if (cmpZero(ptWithFace(pt[p], *f)) > 0) {
				dfs(p, f);
			} else {
				Face &add = faces[tri_num++];
				add.a = b, add.b = a, add.c = p;
				add.flag = 1;
				g[b][a] = g[a][p] = g[p][b] = &add;
			}
		}
	}
	void dfs(int p, Face *f) {
		f->flag = 0;	// remove this face.
		deal(f->b, f->a, p);
		deal(f->a, f->c, p);
		deal(f->c, f->b, p);
	}
	
	int make() {
		if (n < 4)
			return 0;		
		// find a tetrahedron
		bool ok;
		ok = false;
		for (int i = 1; i < n; i++) {
			if (pt[0] != pt[i]) {
				swap(pt[1], pt[i]);
				ok = true;
				break;
			}
		}
		if (!ok)	return 0;
		ok = false;
		for (int i = 2; i < n; i++) {
			if (cmpZero(tri_area(pt[0], pt[1], pt[i]))) {
				swap(pt[2], pt[i]);
				ok = true;
				break;
			}
		}
		if (!ok)	return 0;
		ok = false;
		for (int i = 3; i < n; i++) {
			if (cmpZero(volume(pt[0], pt[1], pt[2], pt[i]))) {
				swap(pt[3], pt[i]);
				ok = true;
				break;
			}
		}
		if (!ok)	return 0;
		
		tri_num = 0;
		for (int i = 0; i < 4; i++) { // init 4 faces. 
			Face &f = faces[tri_num++];
			f.a = (i+1)%4, f.b = (i+2)%4, f.c = (i+3)%4;
			f.flag = 1;
			if (cmpZero(ptWithFace(pt[i], f)) > 0)
				swap(f.b, f.c);
			g[f.a][f.b] = g[f.b][f.c] = g[f.c][f.a] = &f;
		}
		// add point into convex hull
		for (int i = 4; i < n; i++) {
			for (int j = 0; j < tri_num; j++) {
				if (faces[j].flag && cmpZero(ptWithFace(pt[i], faces[j])) > 0) {
					dfs(i, &faces[j]);
					break;
				}
			}
		}
		// remove unused face, trash g[][]
		int tri_n = 0;
		for (int i = 0; i < tri_num; i++) {
			if (faces[i].flag)
				faces[tri_n++] = faces[i];
		}
		tri_num = tri_n; 
		return 1;
	}
	double area() { // surface
		double ret = 0;
		if (n == 3)
			return tri_area(pt[0], pt[1], pt[2]);
		for (int i = 0; i < tri_num; i++)
			ret += tri_area(pt[faces[i].a], pt[faces[i].b], pt[faces[i].c]);
		return ret;
	}
	double volume() {
		double ret = 0;
		Point3D o(0, 0, 0);
		for (int i = 0; i < tri_num; i++)
			ret += volume(o, pt[faces[i].a], pt[faces[i].b], pt[faces[i].c]);
		return fabs(ret);
	}
	Point3D getCenter() {
		Point3D ret(0, 0, 0), o = pt[faces[0].a], p;
		double sum, v;
		sum = 0;
		for (int i = 0; i < tri_num; i++) {
			v = volume(o, pt[faces[i].a], pt[faces[i].b], pt[faces[i].c]);
			p = (pt[faces[i].a] + pt[faces[i].b] + pt[faces[i].c] + o)/4.0;
			if (cmpZero(v) > 0) {
				p = p * v;
				ret = ret + p, sum += v;
			}
		}
		ret = ret / sum;
		return ret;
	}
	int getFaceCount() {
		int ret = 0;
		for (int i = 0; i < tri_num; i++) {
			int ok = 1;
			for (int j = 0; j < i && ok; j++) {
				if (samePlane(faces[i], faces[j]))
					ok = 0;
			}
			if (ok)
				ret++;
		}
		return ret;
	}
	double getInnerClosestDist(Point3D p) { // p in Conver Hull
		double ret = -1;
		for (int i = 0; i < tri_num; i++) {
			Point3D a, b, c;
			a = pt[faces[i].a], b = pt[faces[i].b], c = pt[faces[i].c];
			
			double t = tri_area(a, b, c);
			double v = fabs(volume(a, b, c, p));
			
			if (ret < 0 || v*3/t < ret)
				ret = v*3/t;
		}
		return ret;
	} 
} A, B;
int main() {
	while (scanf("%d", &A.n) == 1) {
		for (int i = 0; i < A.n; i++)
			A.pt[i].read();
		
		scanf("%d", &B.n);
		for (int i = 0; i < B.n; i++)
			B.pt[i].read();
			
		A.make();
		B.make();
		
		double d1, d2;
		d1 = A.getInnerClosestDist(A.getCenter());
		d2 = B.getInnerClosestDist(B.getCenter());
		printf("%lf\n", d1 + d2);
	}
	return 0;
}
/*
8
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
5
0 0 5
1 0 6
-1 0 6
0 1 6
0 -1 6
*/

Read More +

May 19 2015

解題區►解題區 - UVa

UVa 1581 - Pollution Solution

Problem

計算簡單多邊形與半圓的交集面積

Sample Input

Sample Output

1	101.576437872

Solution

Version 1

之前針對簡單多邊形三角剖分，然後去求三角形與圓的關係，還要拆分好幾種可能，考慮共線 … 等複雜操作。

由於最麻煩的地方在於圓與線段之間的關係，想到之前使用 Partition Slab Map，針對 x 座標進行切割，那麼簡單多邊形就會是很多的梯形構成，即便是這樣，梯形還要弄成三角形去跟圓做計算。那換個方式想，直接極角剖分，保證相鄰區間的線段不與圓周相交，接著按照線段中點由遠到近排序，相鄰兩個線段構成梯形，要不全都在內部、外部或者是切一半，切一半也相當好求，拿一個扇形去扣掉一個三角形即可。

算法參考用圖示

#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <assert.h>
#include <vector>
#include <string.h>
using namespace std;
#define eps 1e-9
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
	Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator==(const Pt &a) const {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
	}
	bool operator!=(const Pt &a) const {
    	return !(a == *this);
	}
    bool operator<(const Pt &a) const {
		if (fabs(x - a.x) > eps)
			return x < a.x;
		if (fabs(y - a.y) > eps)
			return y < a.y;
		return false;
	}
	double length() {
		return hypot(x, y);
	}
	void read() {
		scanf("%lf %lf", &x, &y);
	}
};
const double pi = acos(-1);
int cmpZero(double v) {
	if (fabs(v) > eps) return v > 0 ? 1 : -1;
	return 0;
}
double dot(Pt a, Pt b) {
	return a.x * b.x + a.y * b.y;
}
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 cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
	return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
	return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
	Pt s, e;
	int label;
	Seg(Pt a = Pt(), Pt b = Pt(), int l=0): s(a), e(b), label(l) {
	}
	bool operator!=(const Seg &other) const {
		return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
	}
};
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
	if (cmpZero(cross(as, at, bs) * cross(as, at, bt)) < 0 &&
		cmpZero(cross(bs, bt, as) * cross(bs, bt, at)) < 0)
		return 1;
	return 0;
}
Pt getIntersect(Seg a, Seg b) {
	Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
	return acos(dot(va, vb) / va.length() / vb.length());
}
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);
}
int inPolygon(vector<Pt> &p, Pt q) {
	int i, j, cnt = 0;
	int n = p.size();
	for(i = 0, j = n-1; i < n; j = i++) {
		if(onSeg(p[i], p[j], q))
			return 1;
		if(p[i].y > q.y != p[j].y > q.y &&
		q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
		cnt++;
	}
	return cnt&1;
}
double polygonArea(vector<Pt> &p) {
    double area = 0;
    int n = p.size();
    for(int i = 0; i < n;i++)
		area += p[i].x * p[(i+1)%n].y - p[i].y * p[(i+1)%n].x;
    return fabs(area) /2;
}
Pt projectLine(Pt as, Pt ae, Pt p) {
	double a, b, c, v;
	a = as.y - ae.y, b = ae.x - as.x;
	c = - (a * as.x + b * as.y);
	v = a * p.x + b * p.y + c;
	return Pt(p.x - v*a / (a*a+b*b), p.y - v*b/ (a*a+b*b));
}
// 
vector<Pt> circleInterectSeg(Pt a, Pt b, double r) {
	vector<Pt> ret;
	Pt c, vab, p;
	double v, lab;
	c = projectLine(a, b, Pt(0, 0));
	vab = a - b, lab = (a - b).length();
	if (cmpZero(c.x * c.x + c.y * c.y - r * r) > 0)
		return ret;
	v = sqrt(r * r - (c.x * c.x + c.y * c.y));
	vab = vab * (v / lab);
	p = c + vab;
	if (onSeg(a, b, p))
		ret.push_back(p);
	p = c - vab;
	if (onSeg(a, b, p))
		ret.push_back(p);
	if (ret.size() == 2 && ret[0] == ret[1])
		ret.pop_back();
	return ret;
}
bool cmp(pair<double, Pt> a, pair<double, Pt> b) {
    return a.first < b.first;
}
bool cmp2(pair<double, Seg> a, pair<double, Seg> b) {
    return a.first < b.first;
}
double scan(vector<Pt> poly, double r) {
	int n = poly.size();
	vector<Pt> all;
	
	for (int i = 0, j = n-1; i < n; j = i++) {
		all.push_back(poly[i]);
		all.push_back(poly[j]);
		vector<Pt> inter = circleInterectSeg(poly[i], poly[j], r);
		for (int k = 0; k < inter.size(); k++)
			all.push_back(inter[k]);
	}
	sort(all.begin(), all.end());
	all.resize(unique(all.begin(), all.end()) - all.begin());
	
    vector< pair<double, Pt> > polar;
    for (int i = 0; i < all.size(); i++) {
        Pt p = all[i];
        polar.push_back(make_pair(atan2(p.y, p.x), p));
    }
	sort(polar.begin(), polar.end(), cmp);
	
	double ret = 0;
	
	for (int i = 0; i < polar.size(); ) {
		vector<Pt> A, B;
		int idx1, idx2;
		double ltheta, rtheta;
		idx1 = i, ltheta = polar[i].first;
		while (idx1 < polar.size() && cmpZero(polar[i].first - polar[idx1].first) == 0)
			A.push_back(polar[idx1].second), idx1++;
		if (idx1 == polar.size()) // end
			break;
		idx2 = idx1, rtheta = polar[idx1].first;
		while (idx2 < polar.size() && cmpZero(polar[idx1].first - polar[idx2].first) == 0)
			B.push_back(polar[idx2].second), idx2++;
		i = idx1;
		
		if (A.size() == 0 || B.size() == 0)
			assert(false);
		
		for (int j = 0, k = n-1; j < n; k = j++) {
			if (cmpZero(cross(Pt(0, 0), A[0], poly[j])) * cmpZero(cross(Pt(0, 0), A[0], poly[k])) < 0)
				A.push_back(getIntersect(Seg(Pt(0, 0), A[0]), Seg(poly[j], poly[k])));
			if (cmpZero(cross(Pt(0, 0), B[0], poly[j])) * cmpZero(cross(Pt(0, 0), B[0], poly[k])) < 0)
				B.push_back(getIntersect(Seg(Pt(0, 0), B[0]), Seg(poly[j], poly[k])));
		}
		
		A.push_back(Pt(0, 0));
		B.push_back(Pt(0, 0));
		sort(A.begin(), A.end());
		sort(B.begin(), B.end());
		A.resize(unique(A.begin(), A.end()) - A.begin());
		B.resize(unique(B.begin(), B.end()) - B.begin());
		
		vector< pair<double, Seg> > crossEdge;
		for (int p = 0; p < A.size(); p++) {
			for (int q = 0; q < B.size(); q++) {
				if (A[p] == B[q] || A[p] == Pt(0, 0) || B[q] == Pt(0, 0))
					continue;
				for (int j = 0, k = n-1; j < n; k = j++) {
					if (onSeg(poly[j], poly[k], A[p]) && onSeg(poly[j], poly[k], B[q])) {
						Pt mid = (A[p] + B[q]) * 0.5;
						crossEdge.push_back(make_pair((mid - Pt(0, 0)).length(), Seg(A[p], B[q])));
					}
				}
			}
		}
		crossEdge.push_back(make_pair(0.0, Seg(Pt(0, 0), Pt(0, 0))));
		sort(crossEdge.begin(), crossEdge.end(), cmp2);
		for (int j = 0; j < crossEdge.size() - 1; j++) {
			Seg a = crossEdge[j].second;
			Seg b = crossEdge[j+1].second;
			Pt ma = (a.s + a.e) * 0.5;
			Pt mb = (b.s + b.e) * 0.5;
			Pt mab = (ma + mb) * 0.5;
			if (!inPolygon(poly, mab))
				continue;
			double area = (fabs(cross(b.s, b.e, a.e)) + fabs(cross(a.s, a.e, b.s))) /2;
			
			int inout[4] = {}, all_in, all_out;
			inout[0] = cmpZero((a.s - Pt(0, 0)).length() - r) <= 0;
			inout[1] = cmpZero((a.e - Pt(0, 0)).length() - r) <= 0;
			inout[2] = cmpZero((b.s - Pt(0, 0)).length() - r) <= 0;
			inout[3] = cmpZero((b.e - Pt(0, 0)).length() - r) <= 0;
			all_in = inout[0] & inout[1] & inout[2] & inout[3];
			all_out = (!inout[0]) & (!inout[1]) & (!inout[2]) & (!inout[3]);			
//			printf("area %lf\n", area);
//			printf("%lf %lf, %lf %lf\n", a.s.x, a.s.y, a.e.x, a.e.y);
//			printf("%lf %lf, %lf %lf\n", b.s.x, b.s.y, b.e.x, b.e.y);
			if (all_out) {
//				printf("no %lf\n", 0);
				continue;
			}
			if (all_in) {
//				printf("all %lf\n", area);
				ret += area;
				continue;
			}
			if (inout[0] == 1 && inout[1] == 1) {
//				printf("part %lf\n", r * r * (rtheta - ltheta)/2 - fabs(cross(Pt(0, 0), a.s, a.e)) /2);
				ret += r * r * (rtheta - ltheta)/2 - fabs(cross(Pt(0, 0), a.s, a.e)) /2;
			} else {
//				printf("no %lf\n", 0);
			}
		}
//		puts("---");
	}
	
	return ret;
}
int main() {
	int n;
	double r, x, y;
	while (scanf("%d %lf", &n, &r) == 2) {
		vector<Pt> poly;
		for (int i = 0; i < n; i++) {
			scanf("%lf %lf", &x, &y);
			poly.push_back(Pt(x, y));
		}
		
		double ret = scan(poly, r);
		printf("%.9lf\n", ret);
	}
	return 0;
}
/*
6 10
-8 2
8 2
8 14
0 14
0 6
-8 14
4 10
10 0
10 10
-10 10
-10 0
6 10
2 2
12 2
6 4
12 4
8 8
-2 8
5 10
-4 6
-2 2
0 4
4 2
8 4
*/

Version 2

利用類似簡單多邊形的行列式計算面積概念。

由於沒有特別要求把交集情況求出，單純計算純數值，可以用一加一減的方式去求出。

那麼問題只需要考慮圓心與兩點拉出的三角形跟其圓的關係，可以將問題簡化不少，又因為兩點拉出的線段，跟圓只會有三種關係，線段在裡面、線段完全在內側、線段部分在內側。

部分在內側會有兩種情況，兩點都在外面時交圓兩點、一點內一點外交於一點，分開討論計算即可。

#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <assert.h>
#include <vector>
#include <string.h>
using namespace std;
#define eps 1e-9
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
	Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator==(const Pt &a) const {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
	}
	bool operator!=(const Pt &a) const {
    	return !(a == *this);
	}
    bool operator<(const Pt &a) const {
		if (fabs(x - a.x) > eps)
			return x < a.x;
		if (fabs(y - a.y) > eps)
			return y < a.y;
		return false;
	}
	double length() {
		return hypot(x, y);
	}
	void read() {
		scanf("%lf %lf", &x, &y);
	}
};
const double pi = acos(-1);
int cmpZero(double v) {
	if (fabs(v) > eps) return v > 0 ? 1 : -1;
	return 0;
}
double dot(Pt a, Pt b) {
	return a.x * b.x + a.y * b.y;
}
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 cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
	return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
	return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
	Pt s, e;
	int label;
	Seg(Pt a = Pt(), Pt b = Pt(), int l=0): s(a), e(b), label(l) {
	}
	bool operator!=(const Seg &other) const {
		return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
	}
};
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
	if (cmpZero(cross(as, at, bs) * cross(as, at, bt)) < 0 &&
		cmpZero(cross(bs, bt, as) * cross(bs, bt, at)) < 0)
		return 1;
	return 0;
}
Pt getIntersect(Seg a, Seg b) {
	Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
	return acos(dot(va, vb) / va.length() / vb.length());
}
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);
}
int inPolygon(vector<Pt> &p, Pt q) {
	int i, j, cnt = 0;
	int n = p.size();
	for(i = 0, j = n-1; i < n; j = i++) {
		if(onSeg(p[i], p[j], q))
			return 1;
		if(p[i].y > q.y != p[j].y > q.y &&
		q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
		cnt++;
	}
	return cnt&1;
}
double polygonArea(vector<Pt> &p) {
    double area = 0;
    int n = p.size();
    for(int i = 0; i < n;i++)
		area += p[i].x * p[(i+1)%n].y - p[i].y * p[(i+1)%n].x;
    return fabs(area) /2;
}
Pt projectLine(Pt as, Pt ae, Pt p) {
	double a, b, c, v;
	a = as.y - ae.y, b = ae.x - as.x;
	c = - (a * as.x + b * as.y);
	v = a * p.x + b * p.y + c;
	return Pt(p.x - v*a / (a*a+b*b), p.y - v*b/ (a*a+b*b));
}
// 
vector<Pt> circleInterectSeg(Pt a, Pt b, double r) { // maybe return same point
	vector<Pt> ret;
	Pt c, vab, p;
	double v, lab;
	c = projectLine(a, b, Pt(0, 0));
	if (cmpZero(c.x*c.x + c.y*c.y - r*r) > 0)
		return ret;
	vab = a - b, lab = (a - b).length();
	v = sqrt(r * r - (c.x * c.x + c.y * c.y));
	vab = vab * (v / lab);
	if (onSeg(a, b, c + vab))
		ret.push_back(c + vab);
	if (onSeg(a, b, c - vab))
		ret.push_back(c - vab);
	return ret;
}
double circleWithTriangle(double r, Pt a, Pt b) { // get intersect area
	Pt o = Pt(0, 0);
	double la = (a - Pt(0, 0)).length();
	double lb = (b - Pt(0, 0)).length();
	
	if (cmpZero(cross(o, a, b)) == 0)
		return 0;
	
	if (cmpZero(la - r) <= 0 && cmpZero(lb - r) <= 0)
		return fabs(cross(o, a, b))/2;
	
	if (cmpZero(la - r) <= 0 || cmpZero(lb - r) <= 0) {
		if (cmpZero(la - r) > 0)
			swap(a, b), swap(la, lb);
		// a in circle, b not in circle
		vector<Pt> c = circleInterectSeg(a, b, r);
		assert(c.size() > 0);
		
		if (c.size() > 1 && c[0] == a)
			swap(c[0], c[1]);
		double theta = getAngle(c[0], b);
		double ret = 0;
		
		ret += fabs(cross(o, a, c[0]))/2;
		ret += r * r * theta/2;
		
		return ret;
	}
	// a not in circle, b not in circle
	vector<Pt> c = circleInterectSeg(a, b, r);
	if (c.size() == 0) {
		double theta = getAngle(a, b);
		return r * r * theta/2;
	} else {
		assert(c.size() == 2);
		if (dot(c[0] - a, b - a) > dot(c[1] - a, b - a))
			swap(c[0], c[1]);
		double theta1 = getAngle(a, c[0]);
		double theta2 = getAngle(c[1], b);
		double ret = 0;
		
		ret += r * r * (theta1+theta2)/2;
		ret += fabs(cross(o, c[0], c[1]))/2;
		return ret;
	}
	return 0;
}
int main() {
	int n;
	double r, x, y;
	while (scanf("%d %lf", &n, &r) == 2) {
		vector<Pt> poly;
		for (int i = 0; i < n; i++) {
			scanf("%lf %lf", &x, &y);
			poly.push_back(Pt(x, y));
		}
		
		double ret = 0;
		for (int i = 0; i < n; i++) {
			double area = circleWithTriangle(r, poly[i], poly[(i+1)%n]);
			
			if (cmpZero(cross(Pt(0, 0), poly[i], poly[(i+1)%n])) > 0)
				ret += area;
			else
				ret -= area;
		}
		printf("%.9lf\n", fabs(ret));
	}
	return 0;
}
/*
6 10
-8 2
8 2
8 14
0 14
0 6
-8 14
4 10
10 0
10 10
-10 10
-10 0
6 10
2 2
12 2
6 4
12 4
8 8
-2 8
5 10
-4 6
-2 2
0 4
4 2
8 4
*/

Read More +

May 19 2015

解題區►解題區 - UVa

UVa 1566 - John

Problem

撿石子遊戲，但是相反地拿走最後一個的人輸。

(通常 Nim 遊戲都是無法進行操作的人輸)

Sample Input

Sample Output

1 2	John Brother

Solution

上網搜索一下 Sprague Grundy - Jia Zhihao，簡單地說曾經有個大陸人在選訓隊講這個，所以不太算是定理名稱。

有興趣的人可以上網搜尋，主要細分四種狀態，是否每一堆大小都為 1，堆數的奇偶數。剛好有兩個必勝狀態、兩個必輸狀態，彼此之間會相互轉移。

// Anti-SG, Sprague Grundy - Jia Zhihao
#include <stdio.h> 
int main() {
	int testcase, cases = 0;
	int n;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		
		int sg = 0, s1 = 1;
		int x;
		for (int i = 0; i < n; i++) {
			scanf("%d", &x);
			sg ^= x;
			s1 &= x <= 1;
		}
		if (s1)
			printf("%s\n", sg == 0 ? "John" : "Brother");
		else
			printf("%s\n", sg ? "John" : "Brother");
	}
	return 0;
}

Read More +

May 19 2015

解題區►解題區 - UVa

UVa 1558 - Number Game

Problem

給予 2 到 20 的內數字，兩名玩家輪流挑一個數字 x，並且將 x 的倍數遮蔽、x 倍數和已經被遮蔽的數字和也應該被遮蔽。

被遮蔽的數字將無法被使用。無法選擇任何數字的人輸。給定盤面上剩餘可選的數字，請問先手在第一步可以選擇哪幾個數字獲得勝利。

Sample Input

Sample Output

Scenario #1:
The winning moves are: 2.
Scenario #2:
There is no winning move.

Solution

由於數字量很小，可以進行 bitmask 壓縮，來得知數字的使用情況。接著套用博弈 dp 的思路，來得知必勝狀態！

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[1<<20];
int pick(int state, int x) {
	for (int i = x; i <= 20; i += x)
		if ((state>>(i-2))&1)
			state ^= 1<<(i-2);
	
	for (int i = x; i <= 20; i++) {
		if ((state>>(i-2))&1) {
			if (i - x >= 2) {
				if (((state>>(i - x -2))&1) == 0)
					state ^= 1<<(i-2);
			}
		}
	}
	return state;
}
int dfs(int state) {
	if (state == 0)	
		return 0;
	if (dp[state] != -1)	
		return dp[state];
	int &ret = dp[state];
	ret = 0;
	for (int i = 2; i <= 20; i++) {
		if ((state>>(i-2))&1) {
			int v = dfs(pick(state, i));
			ret |= !v;
			if (ret) break;
		}
	}
	return ret;
}
int main() {
	memset(dp, -1, sizeof(dp));
	int testcase, cases = 0;
	int n;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		int mask = 0, x;
		for (int i = 0; i < n; i++) {
			scanf("%d", &x);
			mask |= 1<<(x-2);
		}
		
		printf("Scenario #%d:\n", ++cases);
		vector<int> ret;
		for (int i = 2; i <= 20; i++) {
			if ((mask>>(i-2))&1) {
				int v = dfs(pick(mask, i));
				if (v == 0)
					ret.push_back(i);
			}
		}
		if (ret.size() == 0)
			puts("There is no winning move.");
		else {
			printf("The winning moves are:");
			for (int i = 0; i < ret.size(); i++)
				printf(" %d", ret[i]);
			puts(".");
		}
		puts("");
	}
	return 0;
}

Read More +

May 19 2015

解題區►解題區 - UVa

UVa 1557 - Calendar Game

Problem

給一個起始日期，兩名玩家輪流操作，操作方式有兩種，將日期往後延一天，將月份往後延一個月，抵達 November 4, 2001 的人獲勝，如果發生移動到不合法的日期則視為無效。

必須考慮閏年變化。

Sample Input

Sample Output

1
2
3

YES
NO
NO

Solution

由於年份差最多 100，可以直接根據年月日做狀態搜索。要處理移動時，發生跨年、跨月，這方面會稍微麻煩一點。閏年要額外處理對 2/29 的日期判斷，並且移動時不可超出指定的日期之後。

#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
const int mday[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int dp[128][16][32], used[128][16][32], dcases = 0;
int validDate(int yyyy, int mm, int dd) {
	if (mm < 1 || mm > 12)	
		return 0;
	if ((yyyy%4 == 0 && yyyy%100 != 0) || (yyyy%400) == 0) {
		if (mm == 2) {
			if (dd < 1 || dd > 29)	
				return 0;
		} else {
			if (dd < 1 || dd > mday[mm])
				return 0;
		}			
	} else {
		if (dd < 1 || dd > mday[mm])
			return 0;
	}
	return 1;
}
int complete(int yyyy, int mm, int dd) {
	return yyyy == 2001 && mm == 11 && dd == 4;
}
int fail(int yyyy, int mm, int dd) {
	if (!validDate(yyyy, mm, dd))
		return 1;
	if (yyyy > 2001)	return 1;
	if (yyyy < 2001)	return 0;
	if (mm > 11)		return 1;
	if (mm < 11)		return 0;
	if (dd > 4)			return 1;
	if (dd < 4)			return 0;
	return 0;
}
void nextMonth(int &yyyy, int &mm, int &dd) {
	mm++;
	if (mm == 13)	yyyy++, mm = 1;
}
void nextDay(int &yyyy, int &mm, int &dd) {
	int mday[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
	if ((yyyy%4 == 0 && yyyy%100 != 0) || (yyyy%400) == 0)
		mday[2] = 29;
	dd++;
	if (dd > mday[mm])
		mm++, dd = 1;
	if (mm == 13)	yyyy++, mm = 1;
}
int dfs(int yyyy, int mm, int dd) {
	if (fail(yyyy, mm, dd))
		return 0;
	if (complete(yyyy, mm, dd))
		return 1;
	if (used[yyyy-1900][mm][dd] == dcases)
		return dp[yyyy-1900][mm][dd];
	int &ret = dp[yyyy-1900][mm][dd];
	int y, m ,d;	
	ret = 0, used[yyyy-1900][mm][dd] = dcases;
	
	y = yyyy, m = mm, d = dd;
	nextMonth(y, m, d);
	if (complete(y, m, d))
		ret = 1;
	if (!fail(y, m, d))
		ret |= !dfs(y, m, d);
	
	y = yyyy, m = mm, d = dd;
	nextDay(y, m, d);
	if (complete(y, m, d))
		ret = 1;
	if (!fail(y, m, d))
		ret |= !dfs(y, m, d);
	return ret;
}
int main() {
	int testcase;
	int yyyy, mm, dd;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d %d", &yyyy, &mm, &dd);
		dcases ++;
		printf("%s\n", dfs(yyyy, mm, dd) ? "YES" : "NO");
	}
	return 0;
}
/*
3
2001 11 3
2001 11 2
2001 10 3
*/

Read More +

May 19 2015

解題區►解題區 - UVa

UVa 1534 - Taekwondo

Problem

題目模型與 Zerojudge a192 接線問題一樣。

題目背景在跆拳道選手，有兩團人馬，希望兩兩配對，體重差的絕對值總和越小越好。

Sample Input

Sample Output

1
2

42.1 
23.8

Solution

按照以前的思路來看，維護的是前一個最後匹配到的人是誰，這樣的效率保證是 $O(N^2)$，這樣的效能已經相當快，中間運用到維護最小值的技巧，由於前 i-1 個人匹配到前 j 個人的最小值，那麼 i 匹配到 k 時，需要的是 min(dp[i-1][0 <= j < k])，邊掃描邊維護。

看到網路上有一個不錯的定義，採用失匹配幾個人，較多人數的那一方，將會有幾個人無法匹配，也因此紀錄第 i 個人時，另一團人有 j 個人沒匹配到，那麼當前第 i 個人，必然要與編號 i + j 的人匹配。

忘了提及，一定要先排序，轉換到接線問題時，交錯匹配的距離會比較長，這部分屬於貪心。

#include <stdio.h>
#include <vector>
#include <assert.h>
#include <algorithm>
using namespace std;
int dp[512][512]; // dp[i-th match in A][#miss match in B]
void solve(vector<int> A, vector<int> B) {
	assert(A.size() <= B.size());
	int n1 = A.size(), n2 = B.size();
	int diff = n2 - n1;
	sort(A.begin(), A.end());
	sort(B.begin(), B.end());
	
	for (int i = 0; i < n1; i++) {
		int mn = 0x3f3f3f3f;
		for (int j = 0; j <= diff; j++) {
			if (i == 0)
				mn = 0;
			else
				mn = min(mn, dp[i-1][j]);
			dp[i][j] = mn + abs(A[i] - B[i + j]);
		}
	}
	
	int ret = 0x3f3f3f3f;
	for (int i = 0; i <= diff; i++)
		ret = min(ret, dp[n1-1][i]);
	printf("%d.%d\n", ret/10, ret%10);
}
int main() {
	int testcase;
	int n1, n2, x, y;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &n1, &n2);
		vector<int> A, B;
		for (int i = 0; i < n1; i++) {
			scanf("%d.%d", &x, &y);
			A.push_back(x * 10 + y);
		} 
		for (int i = 0; i < n2; i++) {
			scanf("%d.%d", &x, &y);
			B.push_back(x * 10 + y);
		} 
		
		if (n1 < n2)
			solve(A, B);
		else
			solve(B, A);
	}
	return 0;
}

Read More +

May 19 2015

解題區►解題區 - UVa

UVa 996 - Find the Sequence

Problem

這一題是 UVa 997 - Show the Sequence 的反運算，給定序列找到操作的產生方法。

Sample Input

1 2	3 10 30 30 -30 90 -450 3150 2 2 6 36 360 5400 113400

Sample Output

1 2	[2*[5+[-2]]] [0]

Solution

由於每一個數字不算大，而且從操作方法中得知，數字大小的增長速度非常快，對於累加的部分可以 O(1) 窮舉，但是對於乘積部分需要窮舉因數來得知。

由於題目不是 special judge 也擔心就算找到答案是不是唯一解，按著 Dfs 搜索的順序就 AC 了。之前寫的版本還真是有點微妙。

#include <stdio.h>
#include <set>
#include <vector>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
string num2str(int x) {
    string s;
    stringstream sin(s);
    sin << x;
    return sin.str();
}
int dfs(vector<int> A, int M, string &solution) {
//    printf("[");
//    for (int i = 0; i < A.size(); i++)
//        printf("%d ", A[i]);
//    puts("]");
    int same = 1;
    for (int i = 1; i < A.size(); i++)
        same &= A[i] == A[0];
    if (same == 1) {
        solution = "[" + num2str(A[0]) + "]";
        return 1;
    }
    if (M <= 0)  return 0;
    int g = A[0];
    for (int i = 0; i < A.size(); i++) {
        if (A[i] == 0) {
            g = 0;
            break;
        }
        g = __gcd(g, A[i]);
    }
    for (int i = 1; i < A.size(); i++) {
        if (A[i-1] != 0 && A[i]%A[i-1] != 0)
            g = 0;
        if (A[i-1] == 0 && A[i] != 0)
            g = 0;
    }
    if (g < 0)  g = -g;
    if (g > 0) {
        for (int m = 1; m <= g; m++) {
            if (g%m == 0) {
                vector<int> nA;
                nA.push_back(A[0] / m);
                for (int j = 1; j < A.size(); j++) {
                    if (A[j-1] == 0)
                        nA.push_back(0);
                    else
                        nA.push_back(A[j] / A[j-1]);
                }
                if (dfs(nA, M-1, solution)) {
                    solution = "[" + num2str(m) + "*" + solution + "]";
                    return 1;
                }
                nA.clear();
                nA.push_back(A[0] / (-m));
                for (int j = 1; j < A.size(); j++) {
                    if (A[j-1] == 0)
                        nA.push_back(0);
                    else
                        nA.push_back(A[j] / A[j-1]);
                }
                if (dfs(nA, M-1, solution)) {
                    solution = "[" + num2str(-m) + "*" + solution + "]";
                    return 1;
                }
            }
        }
    }
    vector<int> nA;
    for (int i = 1; i < A.size(); i++)
        nA.push_back(A[i] - A[i-1]);
    if (dfs(nA, M-1, solution)) {
        solution = "[" + num2str(A[0]) + "+" + solution + "]";
        return 1;
    }
    return 0;
}
int main() {
    int M, x;
    string line;
    while (getline(cin, line)) {
        stringstream sin(line);
        sin >> M;
        vector<int> A;
        while (sin >> x)
            A.push_back(x);
        string solution;
        int f = dfs(A, M, solution);
        if (f == 0)
            puts("[0]");
        else
            puts(solution.c_str());
    }
    return 0;
}
/*
 3 10 30 30 -30 90 -450 3150
 2 2 6 36 360 5400 113400
*/

Read More +

May 19 2015

解題區►解題區 - UVa

UVa 953 - The Incredible Pile Machine

Problem

現在有 N 堆，總共有 N 種物品，希望移動最少次，使得每一堆只具有單一種物品。

輸出最小的組合方案。按照第 i 種物品放置在第 j 堆的字典順序最小。

Sample Input

4
3 2 3 4 0 0 2 1 3 1
3 66 66 0 66 66 0 66 66 66
6 476 357 874 50 594 394 320 803 817 348 252 940 453 500 647 299
94 143 800 947 561 885 389 172 301 276 612 130 540 731 774 306 96
239 227 907
2 99 1 1 99

Sample Output

021 9
012 264
251340 12741
01 2

Solution

很明顯地答案會是在某一堆 X 指派給 A 物品，那麼可以減少的移動次數是 X 原本具有 A 的數量。因此答案會是物品述兩總和扣除最大權匹配。

但是答案特別要求輸出字典順序要最小，所以用 KM 算法、最少費用流會稍微麻煩一點，也許多做 $O(N^2)$ 次的窮舉也可以完成。這裡使用 bitmask 的方式去找到最順序最小的最大權匹配。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 10;
int dp[MAXN][1<<MAXN], used[MAXN][1<<MAXN];
int main() {
	int testcase, N;
    int type[20][20];
    scanf("%d", &testcase);
    while (testcase--) {
    	scanf("%d", &N);
    	
    	int sum = 0;
    	for (int i = 0; i < N; i++) {
    		for (int j = 0; j < N; j++)
    			scanf("%d", &type[i][j]), sum += type[i][j];
    	}
    	    	
    	memset(dp, 0, sizeof(dp));
    	memset(used, 0, sizeof(used));
    	for (int i = 0; i < N; i++)
    		dp[0][1<<i] = type[0][i];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < (1<<N); j++) {
				for (int k = 0; k < N; k++) {
					if ((j>>k)&1)	continue;
					dp[i+1][j|(1<<k)] = max(dp[i+1][j|(1<<k)], dp[i][j] + type[i+1][k]);
				}
			}
		}
		
		used[N-1][(1<<N) - 1] = 1;
		for (int i = N-2; i >= 0; i--) {
			for (int j = 0; j < (1<<N); j++) {
				for (int k = 0; k < N; k++) {
					if ((j>>k)&1)	continue;
					if (used[i+1][j|(1<<k)] && dp[i+1][j|(1<<k)] == dp[i][j] + type[i+1][k])
						used[i][j] = 1;
				}
			}
		}
		int ret = dp[N-1][(1<<N)-1];
		for (int i = 0, p, q = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if ((q>>j)&1)
					continue;
				if (used[i][q|(1<<j)]) {
					p = j, q |= 1<<j;
					break;
				}
			}
			printf("%d", p);
		}
		printf(" %d\n", sum - ret);
    }
	return 0;
}

Read More +

May 19 2015

解題區►解題區 - UVa

UVa 905 - Tacos Panchita

Problem

類似磁性場，所有的指針位置都會指向目的地。不過這題的感覺比較像是風向儀，從目的地往外吹動，三角形是風向儀所在的位置，正方形則表示旗幟飄揚的位置。

給定三角形位置，請問正方形的位置在哪裡。

Sample Input

Sample Output

測資參考圖

6 M   P
5 P
4
3  X  PM
2 P
1 M  PM
 1234567

Solution

範例輸出有錯，一開始以為自己寫錯。

由於盤面不大，可以直接進行全盤著色，分成四個象限去著色。當然如果盤面大一點，則必須考慮用外積等方式去完成象限判斷。由於是網格狀，邊界上會比較麻煩，方便起見還是直接著色。

#include <stdio.h> 
#include <string.h>
#include <assert.h>
const int MAXN = 128;
int g[MAXN][MAXN], ret[MAXN][MAXN];
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
int main() {
	int px, py, w, h;
	int cases = 0;
	while (scanf("%d %d %d %d", &px, &py, &w, &h) == 4) {
		assert(w < MAXN && h < MAXN);
		if (cases++)	puts("");
		
		memset(g, 0, sizeof(g));
		memset(ret, 0, sizeof(ret));
		for (int i = 0; i < MAXN; i++) {
			int x, y;
			x = px - i - 1, y = py + i + 1;
			for (int j = 0; j < 2 * (i + 1); j++) {
				if (x >= 0 && x <= w && y >= 0 && y <= h)
					g[x][y] = 1;
				y -= 1;
			}
			x = px - i, y = py + i + 1;
			for (int j = 0; j < 2 * (i + 1); j++) {
				if (x >= 0 && x <= w && y >= 0 && y <= h)
					g[x][y] = 2;
				x += 1;
			}
			x = px + i + 1, y = py + i;
			for (int j = 0; j < 2 * (i + 1); j++) {
				if (x >= 0 && x <= w && y >= 0 && y <= h)
					g[x][y] = 3;
				y -= 1;
			}
			x = px - i - 1, y = py - i - 1;
			for (int j = 0; j < 2 * (i + 1); j++) {
				if (x >= 0 && x <= w && y >= 0 && y <= h)
					g[x][y] = 4;
				x += 1;
			}
		}
		
		for (int i = h; i >= 1; i--) {
			int n, x;
			scanf("%d", &n);
			for (int j = 0; j < n; j++) {
				scanf("%d", &x);
				int tx, ty;
				tx = x + dx[g[x][i] - 1];
				ty = i + dy[g[x][i] - 1];
				ret[tx][ty] = 1;
			}
		}
//		for (int i = 1; i <= w; i++, puts(""))
//			for (int j = 1; j <= h; j++)
//				printf("%d", g[i][j]);
				
		printf("%d %d %d %d\n", px, py, w, h);
		for (int i = h; i >= 1; i--) {
			int n = 0;
			for (int j = 1; j <= w; j++)
				n += ret[j][i];
			printf("%d", n);
			for (int j = 1; j <= w; j++)
				if (ret[j][i])
					printf(" %d", j);
			puts("");
		}
	}
	return 0;
}
/*
3 3 7 6
1 6
1 2
0
1 6
1 2
1 5
*/

Read More +

May 17 2015

學校課程►介面設計

認知風格設計篇

接續上一篇

調整方法

調適能力 (Adaptivity) 與調適性 (Adaptability)。前者能依據使用者的互動 (interaction) 自動修改應用程式的行為，後者則是依照預先定義好的選項來改變應用程式的行為。

網頁設計類型	優點	缺點
Adaptivity	迅速地貼近使用者，使用者不必做過多設定	由於自動變化，對於使用者教學會相當困難
Adaptability	客製化過程有參與感，可以更了解系統功能	入門困難，適應介面到可以客製的過程長

介面初步

test version
		 ______     ______     ______     __  __    
		/\  == \   /\  __ \   /\  __ \   /\ \/ /    
		\ \  __<   \ \ \/\ \  \ \ \/\ \  \ \  _"-.  
		 \ \_____\  \ \_____\  \ \_____\  \ \_\ \_\ 
		  \/_____/   \/_____/   \/_____/   \/_/\/_/ 
		                                            
	+-------------------------------------+     +--------+
	| type you want                       |     |Find it!|
	+-------------------------------------+     +--------+

從最基礎的設計中，明顯地會需要一個輸入框與觸發的按鈕。但是搜尋條件有幾種，從作者、本文、標題、 出版期刊 … 等，這些要怎麼設計才好？

《大神落伍了？這些搜索引擎比 Google 精確還更有趣》這裡提到專門的搜尋引擎，可以針對音樂、圖片、社群、找人 … 等內容進行搜尋。他們是怎麼完成的？

介面二步

test version
		 ______     ______     ______     __  __    
		/\  == \   /\  __ \   /\  __ \   /\ \/ /    
		\ \  __<   \ \ \/\ \  \ \ \/\ \  \ \  _"-.  
		 \ \_____\  \ \_____\  \ \_____\  \ \_\ \_\ 
		  \/_____/   \/_____/   \/_____/   \/_/\/_/ 
		                                            
	+-----------+  +--------+  +-------+        +--------+
	| BOOK NAME |  | AUTHOR |  | WHERE |        |Find it!|
	+-----------+  +--------+  +-------+        +--------+

這裡的設計多了三個欄位，有些欄位可填、可不填，進行分開的搜尋。然而會不會發生有人誤填一些資訊，誤把人名當書名，造成搜尋結果不好。為了考量這些，基本上都是在搜尋結果中做一個排序，排序的優先權可能先按照書名、作者、地點。搜尋方式的比例差異通常呈現普遍性。

為了加速篩選結果，通常會先抓書名，如果書名不夠具有特色，則會嘗試抓作者名稱，如果作者出版很多本書，則會考慮出版時間、內容。能按照內容進行搜索的引擎，肯定規模很大。

		 ______     ______     ______     __  __    
		/\  == \   /\  __ \   /\  __ \   /\ \/ /    
		\ \  __<   \ \ \/\ \  \ \ \/\ \  \ \  _"-.  
		 \ \_____\  \ \_____\  \ \_____\  \ \_\ \_\ 
		  \/_____/   \/_____/   \/_____/   \/_/\/_/ 
		                                            
	+-----------+  +--------+  +-------+        +--------+
	| BOOK NAME |  | AUTHOR |  | WHERE |        |Find it!|
	+-----------+  +--------+  +-------+        +--------+
 
+---------------+---------------+---------------------+
|  BOOK NAME    |  AUTHOR       |  WHERE              |
+---------------+---------------+---------------------+
                                                       
+---------------+                                      
|  TITLE        |                                      
+---------------+                                      
|  SUBTITLE     |                                      
+---------------+                                      
|  CHAPTER      |                                      
+---------------+                                      
|  NICKNAME     |                                      
+---------------+                                      
|  PROLOGUE     |                                      
+---------------+

有一種方式是提供搜尋條件的細節，來增加使用者的搜尋效率。上面就是一個範例，不僅僅只是官方書名提供搜索，細節劃分也是相當重要。甚至有人會將書給予暱稱，例如書的名稱太普通，卻以某種封裝、寫法出名，那麼這些書的名稱可能就比較特別。

對於場依賴的而言，看得到的搜尋介面相當重要，它們比較容易根據環境提供的條件，因此設計效能上影響很多。反過來看看場獨立的人，對於這個介面操作可能會將自己的想法投入，這些想法可能來自於自身或者是之前學習過的知識。

argument version
		 ______     ______     ______     __  __    
		/\  == \   /\  __ \   /\  __ \   /\ \/ /    
		\ \  __<   \ \ \/\ \  \ \ \/\ \  \ \  _"-.  
		 \ \_____\  \ \_____\  \ \_____\  \ \_\ \_\ 
		  \/_____/   \/_____/   \/_____/   \/_/\/_/ 
		                                            
	+-------------------------------------+     +--------+
	| learning in 23 days type:reference  |     |Find it!|
	+-------------------------------------+     +--------+

對於隱藏式的操作想必也是相當上手。但這種使用需要教學，不是相當方便。可以由簡到繁地引領使用者，例如說第一次搜尋操作後，自動填充，提示使用者下一次搜尋的方法。

1
2
3

+-------------------------------------+     *--------*
| learning in 23 days                 |     |Find it!| <--- click
+-------------------------------------+     *--------*

得到結果後

	+-------------------------------------+     +--------+
	| learning in 23 days type:reference  |     |Find it!|
	+-------------------------------------+     +--------+
----------------------------------------------------------------------
Find result with ...
* learning in 23 days, author:Alice, type:reference
	detail ...
* ...

現在的設計大多都是由 簡到繁 的方式，從蘋果軟體中都可以發現到這些特徵，將不常用的功能都先藏在特定的地方，先基礎地提供最低需求，當使用者發現結果越來越不好時，主動地去察覺要怎麼使用更複雜的操作。

介面三步

當然有些人搜尋的結果，會根據場依賴、場獨立來查閱，場依賴偏向是由觀眾評分、評論來判定是否找到正確的書，場獨立純文本內容為主。著重的觀點不同，為了成功銷售所有的書籍，顯示的方法如下兩種參考。

----------------------------------------------------------------------
Find result with ...
* Learning in 23 days, author:Alice, type:reference
	detail ...
* WTF Learning, author:Blob
	detail ..

----------------------------------------------------------------------
Find result with ...
* [HOT] STAR: 5, learning in 23 days, author:Alice, type:reference
	detail ...
* STAR: 3, WTF Learning, author:Blob
	detail ..
* ...

以上示範的是場獨立、依賴的兩種。當然上面的設計屬於階層式、也有水平擺放訊息的方式。其實還有很多種的！

* 1 TITLE AUTHOR 
	* 1.1 DETAIL
	* 1.2 DETAIL
		* 1.2.1 DETAIL

+-------+   +------------------------------------------+
|       |   |  TITLE                                   |
|       |   +------------------------------------------+
| COVER |                                               
|       |   +------------------------------------------+
|       |   |  AUTHOR, DETAIL                          |
|       |   |                                          |
+-------+   +------------------------------------------+

如果找書不根據任何別人推坑的想法，階層式會是很好的細節來決策，嘗試把每一本書的概要都仔細讀過，階層式很吃 優先權順序 ，設計起來相當挑戰。

如果是下方的方式，比較偏向大致上已經在事前知道要買哪本書，有了大概目標。這樣的設計方式方便跳躍性的搜索，因為階層式會 改變高度 ，檢索時的位移量不同會造成操作時間會比較久，但是下方的那種方式屬於固定位移量。

至於對色彩學的配色部分，又分單色、雙色欄位，來加快視窗滑動的對齊。而每一個欄位的文字色彩也相當講究，用色數量越多，看起來越五花八門，面向的使用族群也越多。為了讓使用者有 貼切感 (服務的專一性)，通常用色不大於三種。

回頭調整

Adaptivity 提供系統自動調整變化，最好提醒使用者可以切換回去舊的介面設計，否則多個使用者在現實中交談時，可能會發生矛盾的錯亂交流。

Adaptability 提供使用者自定義，這些功能從系統中抽離出來，對於開發者來說是件好事，讓所有功能盡可能地讓特定使用者使用，但普遍性來說，大多數的功能都會被忽略，甚至當作從來沒有過。

Adaptability 類型的網頁設計，提供高度穩定性、客製化，有利於長時間的網站經營，培養長遠的顧客為主，對於短期入門的新手而言，對於客製化的吃力程度不一，當尚未熟悉系統前，對於功能設定處於一知半解狀態，需要閱讀文檔或累積經驗。因此在使用前期效率並不高，有待一段時間後，使用效率就有機會突破 Adaptivity 類型的。

正因為使用時間的長短，Adaptability 比較適合高頻率使用的軟體，而且功能性很強。相較於 Adaptivity 給予功能性較低，但操作起來會比較耗時 (滑鼠移動、滾動) 的軟體。

Reference

Evaluation of a personalized digital library based on cognitive styles: Adaptivity vs. adaptability

課程需求才看得，雖然我對裡面的實驗方法一點也不認同，很多地方沒有考慮進去，實驗的順序性有考慮到，卻沒有去考慮適應面向的主體，拿幾次任務的時間來進行比較往往是不夠的，根據時間成長的效率比較也應該被提出。

課程公告

由於明天的課程有多數同學因畢業旅行而無法前來上課，因此明天上課的方式將不在課堂上進行，而改為同學閱讀所附的 paper，並找時間與組員討論所附的問題

請容許我罵一聲！我擦！為什麼不上課！雖然老師上課的認知風格與我不同，無法好好地學習知識，在盡可能地去適應，卻不斷地減少上課次數，學期結束前都還沒有適應吧。

Read More +