marker切奇数题�Q�我切偶数题

LSM — Mon, 17 Sep 2007 12:17:00 GMT

1�?a >http://acm.pku.edu.cn/JudgeOnline/problem?id=1474
2�?a >http://acm.pku.edu.cn/JudgeOnline/problem?id=2794
3�?a >http://acm.pku.edu.cn/JudgeOnline/problem?id=1366
4�?a >http://acm.pku.edu.cn/JudgeOnline/problem?id=1392
5�?a >http://acm.pku.edu.cn/JudgeOnline/problem?id=2169

6�?a >http://acm.pku.edu.cn/JudgeOnline/problem?id=3150
7�?a >http://acm.pku.edu.cn/JudgeOnline/problem?id=1400
8�?a >http://acm.pku.edu.cn/JudgeOnline/problem?id=2065
9�?a >http://acm.pku.edu.cn/JudgeOnline/problem?id=1860
10�?a >http://acm.pku.edu.cn/JudgeOnline/problem?id=2168

11�?a >http://acm.pku.edu.cn/JudgeOnline/problem?id=2791
12�?a >http://acm.pku.edu.cn/JudgeOnline/problem?id=2532
13�?a >http://acm.pku.edu.cn/JudgeOnline/problem?id=1712
14�?a >http://acm.pku.edu.cn/JudgeOnline/problem?id=1709
15�?a >http://acm.pku.edu.cn/JudgeOnline/problem?id=1457

16�?a >http://acm.pku.edu.cn/JudgeOnline/problem?id=1134
17�?a >http://acm.pku.edu.cn/JudgeOnline/problem?id=1137
18�?a >http://acm.pku.edu.cn/JudgeOnline/problem?id=1481

LSM 2007-09-17 20:17 发表评论

计算几何相关模板�Q�更��C��……）

LSM — Wed, 22 Aug 2007 10:39:00 GMT

计算几何相关模板�Q�更��C��……�Q?br>

最�q�在学计��几何，边学�Q�边整理模板�Q�有错的话请大家指出�Q?br>

1//计算几何模板 ~ alpc02
2const double PRECISION = 1e-8;
3struct Point {
4    double x, y;
5};
6int dblcmp(double d) {
7    return (fabs(d) < PRECISION) ? 0:(d>0 ? 1:-1);
8} //三叉口函敎ͼ�避免�_�ֺ�误差
9double length(double x, double y) {
10    return sqrt(x*x + y*y);
11} //向量长度
12double dotdet(double x1, double y1, double x2, double y2) {
13    return x1*x2 + y1*y2;
14} //点积
15double det(double x1, double y1, double x2, double y2) {
16    return x1*y2 - x2*y1;
17} //叉积
18int cross(const Point &a, const Point &c, const Point &d) {
19    return dblcmp( det(a.x-c.x, a.y-c.y, d.x-c.x, d.y-c.y) );
20} //��x��螺旋定则�Q?——a在cd右侧�Q?1——a在cd左侧�Q?——三点共�U?/span>
21bool between(const Point &a, const Point &c, const Point &d) {
22    return dblcmp( dotdet(c.x-a.x, c.y-a.y, d.x-a.x, d.y-a.y) ) != 1;
23} //在cross(a,c,d)==0的基��上，可判断点a是否在cd内部
24int segIntersect(const Point &a, const Point &b, const Point &c, const Point &d) {
25    int a_cd = cross(a,c,d);
26    if(a_cd == 0 && between(a,c,d))    return 2;
27    int b_cd = cross(b,c,d);
28    if(b_cd == 0 && between(b,c,d))    return 2;
29    int c_ab = cross(c,a,b);
30    if(c_ab == 0 && between(c,a,b))    return 2;
31    int d_ab = cross(d,a,b);
32    if(d_ab == 0 && between(d,a,b))    return 2;
33    if ((a_cd ^ b_cd) == -2 && (c_ab ^ d_ab) == -2)
34        return 1;
35    return 0;
36} //两线�D늛�交情况：0——不�怺��Q?——规范相交，2——不规范�怺��Q�交于端�Ҏ��重合�Q?/span>
37void intersectPoint(const Point &a, const Point &b, const Point &c, const Point &d, Point &e) {
38    double sc, sd;
39    sc = fabs( det(b.x-a.x, b.y-a.y, c.x-a.x, c.y-a.y) );
40    sd = fabs( det(b.x-a.x, b.y-a.y, d.x-a.x, d.y-a.y) );
41    e.x = (sc * d.x + sd * c.x) / (sc + sd);
42    e.y = (sc * d.y + sd * c.y) / (sc + sd);
43} //两线�D�规范相交时�Q�求交点坐标
44int linesegIntersect(const Point &a, const Point &b, const Point &c, const Point &d) {
45    int c_ab = cross(c,a,b);
46    if(c_ab == 0)    return 2;
47    int d_ab = cross(d,a,b);
48    if(d_ab == 0)    return 2;
49    if(c_ab ^ d_ab == -2)
50        return 1;
51    return 0;
52} //直线ab和线�D�cd�怺�情况�Q?——不�怺��Q?——规范相交，2——不规范�怺��Q�交于端�Ҏ��重合�Q?/span>
53int lineIntersect(const Point &a, const Point &b, const Point &c, const Point &d) {
54    if(dblcmp(det(b.x-a.x, b.y-a.y, d.x-c.x, d.y-c.y)) != 0)
55        return 1;
56    if(cross(a,c,d) == 0)
57        return 2;
58    return 0;
59} //两直�U�相交情况：0——��^行，1——规范相交，2——不规范�怺��Q�重合）
60

LSM 2007-08-22 18:39 发表评论

计算几何入门题（更新中……）

LSM — Wed, 22 Aug 2007 10:28:00 GMT

摘要: 计算几何入门题（更新�?#8230;…�Q?http://acm.pku.edu.cn/JudgeOnline/problem?id=1696Space Ant用到叉积�Q�点�U�。这个题的代码稍微改改，貌似可以认�ؓ是凸包的o(n^2)��法�Q�即卷包心菜�?Code highlighting produced by Actipro CodeHighlighter (freeware)http... 阅读全文

LSM 2007-08-22 18:28 发表评论

POJ 3351 —�?Gerrymandering

LSM — Wed, 22 Aug 2007 03:30:00 GMT

http://acm.pku.edu.cn/JudgeOnline/problem?id=3351
Gerrymandering
难！O(n^3)的dp�Q�降为接�q�O(n^2)才能�q��?br>
不难惛_��O(n^3)的dp�Q�dp[k][t]代表前k个riding合�ƈ成t块（也就是说合�ƈk-t�ơ）�Q�所能取得的最大��|��赢的riding个数减去输的riding个数�Q�。定义w[i][j]代表i至j合�ƈ一起后的输赢状态，1�?1�?br>1、dp[0][0] = 0�Q�状态�{�U�L��E�dp[k][t] = max(dp[k'][t-1] + win[k'+1][k]), 0<=k'2、目标则是max(t) 使得dp[n][t] > 0�Q�输出答案n-t�?br>转移的复杂度是o(n)�Q�这��h��们的复杂度就是O(n^3)�Q�必��降低复杂度�?br>
��x��Q�我们求dp[k][t]�Ӟ��遍历了一�ơdp[k'][t-1]�Q�当我们再求dp[k+1][t]�Ӟ��q�需要再遍历一�ơdp[k'][t-1]�Q�只不过�q�个时候k'范围增加�?。那我们能否在求dp[k][t]遍历dp[k'][t-1]时把�q�些有用信息记录下来供求dp[k+1][t]时用呢？

看状态�{�U�L��E�：dp[k][t] = max(dp[k'][t-1] + win[k'+1][k])
问题�Q�受win[k'+1][k]影响�Q�dp[k'][t-1] 的最大��|��加上win[k'+1][k]后�ƈ不一定是dp[k][t]的最大�?br>但是�Q�仔�l�看会发玎ͼ�win[k'+1][k]仅有两种取��|��1�?1,而且当k'变化时dp[k'][t-1]的值相�?�?�?
�q�样的话�Q�方�E�可以写成：dp[k][t] = maxdp + win[k''+1][k]�Q�这里maxdp = max(dp[k'][t-1])�Q�k''有一个限�Ӟ��是�Q�dp[k''][t-1]必须�{�于maxdp�?br>一旦�{换成�q�类方程后，dp[k'][t-1]的信息就可以重复利用�Q�状态�{�Uȝ��复杂度大大降低�?br>
实现�Q�记录maxdp�Q�然后徏一个list�Q�记录满��dp[k''][t-1] = maxdp的k'’�Q�实时更新list�Q�每�ơ只需从list里�{�Uȝ��态就行�?br>优化�Q�一旦从list里找��C��个k''�Q�满��win[k''+1][k]=1�Q�那么dp[k][t] = maxdp + 1�Q�dp[k][t]的计��就可马上结束�?br>

1 //POJ_3351 �?nbsp;alpc02
2 #include <algorithm>
3 using namespace std;
4
5 const int INF = 12345678;
6 const int N = 1010;
7 const int P = 12;
8
9 int n, p;
10 int v[N][P];
11 int win[N][N];
12 int dp[N][N];
13
14 int Max(int a,int b){return a>b ? a:b;}
15 void input() {
16     scanf("%d", &n);
17     scanf("%d", &p);
18     int i, j, k;
19     memset(v[0], 0, sizeof(v[0]));
20     for(i=1; i<=n; i++)
21         for(j=1; j<=p; j++) {
22             scanf("%d", &k);
23             v[i][j] = v[i-1][j] + k;
24         }
25 }
26 void init() {
27     int i, j, k, vote;
28     for(i=1; i<=n; i++)
29         for(j=i; j<=n; j++) {
30             vote = v[j][1] - v[i-1][1];
31             for(k=2; k<=p; k++)
32                 if(v[j][k] - v[i-1][k] >= vote)
33                     break;
34             if(k > p)    win[i][j] = 1;
35             else        win[i][j] = -1;
36         }
37 }
38 int solve() {
39     init();
40
41     int i, j, k, t;
42     int list[N], top, mx;
43     dp[0][0] = 0;
44     for(j=1; j<=n; j++) {
45         top = 0;
46         mx = -INF;
47         for(i=j; i<=n; i++) {
48             if(dp[i-1][j-1] > mx) {
49                 mx = dp[i-1][j-1];
50                 list[0] = i-1;
51                 top = 1;
52             }
53             else if(dp[i-1][j-1] == mx)
54                 list[top++] = i-1;
55             for(t=0; t<top-1; t++)
56                 if(win[list[t]+1][i] == 1)
57                     break;
58             dp[i][j] = mx + win[list[t]+1][i];
59         }
60     }
61
62     int ans;
63     for(ans=n; ans>=1; ans--)
64         if(dp[n][ans] > 0)
65             return n-ans;
66     return -1;
67 }
68 int main() {
69     input();
70     printf("%d\n", solve());
71     return 0;
72 }

LSM 2007-08-22 11:30 发表评论

LSM — Tue, 21 Aug 2007 00:52:00 GMT

计算几何初步认识

—�?/span>Wjx昨晚�l�我速成的计��几�?/span>

一�?/span>炏V�?/span>

l 点的坐标A(x1, y1)�Q?/span>B(x2, y2)

二�?/span>向量�?/span>

l 向量AB = (x2-x1, y2-y1) = (x3,y3) �Q?/span>CD = (x4, y4)�?/span>

l 向量的模|AB| = sqrt(x3*x3 + y3*y3) 卛_��量的长度�?/span>

三�?/span>点积�?/span>

l 点积的结果�ؓ一个数倹{�?/span>

l 数��D��方�?/span>AB * CD �Q?/span> x3*x4 + y3*y4�?/span>

l 几何意义AB * CD = |AB| * |CD| * cos(a)�Q?/span>a为向�?/span>AB逆时针�{�?/span>CD的角度，0<=a<360�Q�也可以认�ؓ是两向量的夹角，0<=a<=180。一般用于求夹角�Q?/span>a = acos( (AB * CD) / (|AB| * |CD|) )。也可：|CD| * cos(a) = AB * CD / |AB|�Q�即向量CD�?/span>AB上的投媄�?/span>

四�?/span>叉积�?/span>

l 叉积的结果�ؓ一个向量�?/span>

l AB×CD数�?/span>= x3*y4 – x4*y3�?/span>

l 方向由右手螺旋定则判定�?/span>

l 几何意义�Q?/span>AB×CD = |AB| * |CD| * sin(a)�Q�取�l�对值即是以AB�?/span>CD��的��^行四边�Ş面积�?/span>

五�?/span>�U�段�怺�的判定（判定�U�段AB和线�D?/span>CD是否�怺��Q�属于哪�U�相交）�?/span>

l 规范�怺��Q�交点只有一个，且不是线�D늚�端点�?/span>

1�?/span>充要条�g�Q�点A和点B�?/span>CD的两侧�ƈ且点C和点D�?/span>AB的两侧�?/span>

2�?/span>如何判断�?/span>A在向�?/span>CD的左侧还是右侧：CA×CD的数值大�?/span>0则左侧，��于0则右侧。于�?/span>CA×CD的数值和CB×CD的数值异��P��?/span>A和点B�?/span>CD的两侧，同理可判断点C和点D是否�?/span>AB的两侧（注意�Q�必��M��格异��P��?/span>

l 不规范相交：交点为某个线�D늚�端点�Q�甚至两�U�段有一�D�重合�?/span>

1�?/span>充要条�g�Q�一条线�D늚�一个端点在另一条线�D�上。即A�?/span>CD上或B�?/span>CD上或C�?/span>AB上或D�?/span>AB上�?/span>

2�?/span>A在线�D?/span>CD上的充要条�g�Q?/span>

a) AC×AD = 0�Q�几何意义，AC�?/span>AD�l�成的��^行四边�Ş的面�U��ؓ0�Q�即A�?/span>C�?/span>D三点��q��?/span>

b) A点在CD之间�Q?/span>A.x处于C.x�?/span>D.x之间�q�且A.y处于C.y�?/span>D.y之间

LSM 2007-08-21 08:52 发表评论

最新国产成人在线观看,欧美精品 国产精品,国产一区二区三区在线观看免费视频

marker切奇数题�Q�我切偶数题

计算几何相关模板�Q�更��C��……）

计算几何入门题（更新中……）

POJ 3351 —�?Gerrymandering

最新国产成人在线观看,欧美精品国产精品,国产一区二区三区在线观看免费视频