Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

受不了了........看看我的O(CLogC)的主过程有什么不对吧.....

Posted by Bluebird at 2005-07-21 20:21:17 on Problem 2500

 已排序
 cc[i](0<=i<=c-1)为第i个可选点
 p为前半弧指针，q为后半弧指针，mid为弧的中间点
 getarea计算三点组成的面积
 getmax得到两数的较大值
 area保存着最优值

		p = 1;
		q = 2;
		area = 0;
		for (i = 2; i < c - 1; i ++)
		{
			mid = cc[i] / 2;
			while ((p < i - 1) && (cc[p] < mid)) p ++;
			now = getmax(getarea(0, cc[i], cc[p]), getarea(0, cc[i], cc[p - 1]));
			mid = (n + cc[i]) / 2;
			while ((q < c - 1) && (cc[q] < mid)) q ++;
			now += getmax(getarea(0, cc[i], cc[q]), getarea(0, cc[i], cc[q - 1]));
			area = getmax(area, now);
		}

Followed by:

刚才表述有歧义.................主过程是O(C)的...... (2) Bluebird 2005-07-21 20:24:17
- Bluebird要bg了，这么多人折腾这么久 (4) frkstyc 2005-07-22 13:02:02
  - 支持，bluebird，住哪？ (0) sunmoonstar_love 2005-07-22 13:20:31
  - 感谢党....感谢人民政府..... (0) Bluebird 2005-07-23 16:54:39
    - 你们写的那么快，我折腾半天,才62ms (0) sunmoonstar_love 2005-07-23 16:57:01
Re:受不了了........看看我的O(CLogC)的主过程有什么不对吧..... (93) c0500448242 2005-07-21 20:30:04
- cc[i]表示第i个可选点的编号，一段弧中选一个点要尽量接近弧的中点吧，所以我求出第一个过了中点的点 (2) Bluebird 2005-07-21 20:31:39
  - 没过中点的不可能更接近中点? (4) c0500448242 2005-07-21 20:32:17
    - 不是的，接近中点的点肯定在中点两侧（或者就是中点），我后面有个getmax(getarea, getarea)，就是考虑了左右两侧的情况 (0) Bluebird 2005-07-21 20:33:17
      - 嗯, 好像没有错. (0) c0500448242 2005-07-21 20:38:58
        我排序应该不会错，直接调用的qsort......求面积我设坐标用行列式和直接ABsinC/2都用了.....but... (0) Bluebird 2005-07-21 20:40:41
        我做的时候错在c*g>2^32 (0) c0500448242 2005-07-21 20:42:44
        看来你做几何的时候头脑会不清醒 (0) frkstyc 2005-07-21 20:43:42
        差不多, 看到计算几何就头痛, 怕了它了. (0) c0500448242 2005-07-21 20:46:18
        hands up and get shot! (0) frkstyc 2005-07-21 20:49:18
        汗..... 1(\n) 123 654321 123 542 这组数据我算出来硬是只有68.XXXX，答案是70.XXXX....我真想不通..... (0) Bluebird 2005-07-21 20:51:20
        我不像你什么题都能做, 我一般看到要求精度的题就闪, 不过这周是躲也躲不过了. (0) c0500448242 2005-07-21 20:52:30
        don't say such words... esp. those about me (0) frkstyc 2005-07-21 20:55:31
        :) (0) c0500448242 2005-07-21 20:57:37
        no exercise contest on sunday (0) frkstyc 2005-07-21 21:00:06
        我 __int64(g) * c .... (0) Bluebird 2005-07-21 20:44:23
主过程没有问题. (547) c0500448242 2005-07-21 20:57:01
- 分过程 ------> (635) Bluebird 2005-07-21 21:00:33
  - 默认0点坐标为(d,0) (2) Bluebird 2005-07-21 21:03:22
  - wrong! (691) frkstyc 2005-07-21 21:03:36
    - if you find out the problem yourself perhaps you will kill yourself (0) frkstyc 2005-07-21 21:04:41
    - where ............ (0) Bluebird 2005-07-21 21:04:41
      - d>>=1,what if d is odd?????????????????????????????????????????????????? (0) frkstyc 2005-07-21 21:05:06
        我靠..................................................... (0) Bluebird 2005-07-21 21:05:45
        让我撞死吧，豆腐！！！！！！ (0) Bluebird 2005-07-21 21:07:12
        ft.. (0) frkstyc 2005-07-21 21:07:50
        sign........怎么还wa......不会是出现精度问题了吧........ (0) Bluebird 2005-07-21 21:22:18
- 用ABsinC/2求面积 ----> (399) Bluebird 2005-07-21 21:02:19
  - d = d * d / 4.0 .... (2) Bluebird 2005-07-21 21:25:04
  - 我用的是向量差积算面积 (439) windbells 2005-07-21 22:27:07
    - 汗....那不就是行列式.... (0) Bluebird 2005-07-22 12:30:40
兄弟们救我啊....... (2) Bluebird 2005-07-21 21:33:11
- 经测试, 精度似乎也没有问题. (4) c0500448242 2005-07-21 21:37:34
  - sign...那是啥问题啊.....我rp还可以的啊！！！！1(\n) 1000 1000000000 500 123456789 这个数据我跟它差0.000023 (0) Bluebird 2005-07-21 21:40:11
    - PI的精度至少要到3.14159265359, 少一位都会WA (0) c0500448242 2005-07-21 21:43:13
      - 我靠............我再次无语................................. (0) Bluebird 2005-07-21 21:45:13
      - 哭.......还有一个点wa....差了10....我pi已经改成acos(-1)了........ (0) Bluebird 2005-07-21 21:54:15
      - Re:PI的精度至少要到3.14159265359, 少一位都会WA: 没那么夸张，代码控制的好，3.1415926也能AC (0) sunmoonstar_love 2005-07-21 22:14:20
        我用自己的代码试的, 至于别人怎样我也说不准. (0) xfxyjwf 2005-07-21 22:31:51
        那提供一下求面积的其他方法把....... (0) Bluebird 2005-07-22 11:59:32
      - 那个那个～可以用ABsinC/2么？貌似sin的精度很低很低啊～～ (0) ACM06Louty 2007-10-16 19:12:30
        第二组样例我就差了0.0000005左右。。。。 (0) ACM06Louty 2007-10-16 19:13:35
        乱猜 (0) frkstyc 2007-10-16 19:19:21
        ？？～我程序只要有sin或者cos就从来没有A过……5555555555 (0) ACM06Louty 2007-10-16 19:24:30
        可是我实在不知道除了sin哪里还有影响精度的问题，按说四则运算都没问题吧。。 (0) ACM06Louty 2007-10-16 19:32:07
        程序…… (141) ACM06Louty 2007-10-16 19:36:34
    - 能给几组数据吗？ (0) c0500448129 2005-07-21 22:04:32
      - 发到你163的邮箱了 (0) Bluebird 2005-07-22 12:23:58
        谢谢！ (0) c0500448129 2005-07-22 12:50:17
      - 最后一对数据就是这道题的 (0) Bluebird 2005-07-22 12:28:49
兄弟们，除了变量定义我的过程都贴了......救救我吧..... (0) Bluebird 2005-07-22 11:59:41
- 正在做计算几何的模版，郁闷中，有心无力 (0) sunmoonstar_love 2005-07-22 12:02:04
- send me your complete code (0) frkstyc 2005-07-22 12:03:07
- Re:兄弟们，除了变量定义我的过程都贴了......救救我吧..... (1575) c0500448242 2005-07-22 12:04:35
  - sigh......为啥你过了....... (0) Bluebird 2005-07-22 12:23:26
    - 被3/2 != 1.5郁闷了 :) (0) c0500448242 2005-07-22 12:53:49
      - 这段时间才用的C...真是细节问题害死人啊............ (0) Bluebird 2005-07-22 12:57:14
      - 哈哈，一般这时候我都加个(double), 或是*1.0, 也是郁闷后的教训 (0) sunmoonstar_love 2005-07-22 12:58:51
  - Re:兄弟们，除了变量定义我的过程都贴了......救救我吧..... (12) chengmingvictor 2005-07-29 22:09:23
    - Re:兄弟们，除了变量定义我的过程都贴了......救救我吧..... (23) chengmingvictor 2005-07-29 22:30:35

Post your reply here:

Home Page Go Back To top