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(c^2logc)，再高就不行了，最低应该是O(clogc)，O(logc)的写出来过不了

Posted by frkstyc at 2005-07-20 18:29:08 on Problem 2500
In Reply To:复杂度应该做到多少？ Posted by:scu05p07 at 2005-07-20 18:27:26

Followed by:

不考虑点的位置，是不是当四边形为正方形时，面积最大？那么是不是追求近似正方形？ (0) sunmoonstar_love 2005-07-20 20:38:01
- 这样子搞不行的 (0) frkstyc 2005-07-20 20:38:19
- Rainer就是这样搞死的…… (0) TN 2005-07-20 20:39:03
  - 我死得更悲壮…… (0) frkstyc 2005-07-20 20:39:34
- 还好，我还没实践，那是怎么搞的？ (0) sunmoonstar_love 2005-07-20 20:40:23
  - 0*g%c那个点必选，枚举从这个点出发的对角线，然后再找另外两点 (0) frkstyc 2005-07-20 20:41:07
    - 谢谢 (0) sunmoonstar_love 2005-07-20 20:44:14
    - 为什么这个点必选啊？ (0) c0500448129 2005-07-20 20:45:50
      - 假如不选的话转呀转就转回去了嘛 (0) frkstyc 2005-07-20 20:46:17
        有这样的对称性吗？ (0) c0500448129 2005-07-20 20:48:21
        他的那个Generate就保证了这点 (0) TN 2005-07-20 20:48:47
        不懂了。你们是说那个0点，一定是4个点之一？ (0) c0500448129 2005-07-20 20:50:42
        假如其他的可以的话，这个一定也可以 (0) frkstyc 2005-07-20 20:51:11
        styc,你在哪个寝室？我上来问你吧。 (0) c0500448129 2005-07-20 20:55:27
        你上面的对门 (0) frkstyc 2005-07-20 20:55:55
        (g * k) mod n,k=0时候那个点固定的阿 (0) TN 2005-07-20 20:51:45
      - 也就是至少先选个起点，总得有第一个点的 (0) sunmoonstar_love 2005-07-20 20:47:38
    - 另外两点也就是两端圆弧最中间的一个或两个点吧？就像底边固定，找个最大的高，这样复杂度是 2*c吧 (0) sunmoonstar_love 2005-07-20 20:57:58
      - 是这意思么？ (0) sunmoonstar_love 2005-07-20 20:58:31
    - 终于搞明白了，谢谢两位！我还和司徒说了刚想出来的O(c)的算法。 (0) c0500448129 2005-07-20 21:04:44
      - 实现起来我会头大 (0) frkstyc 2005-07-20 21:05:08
      - rainer你写一下看看时间 (0) frkstyc 2005-07-20 21:06:05
        好，晚点再写。 (0) c0500448129 2005-07-20 21:07:35
      - 我说那个对么？ (0) sunmoonstar_love 2005-07-20 21:06:46
        对de (0) c0500448129 2005-07-20 21:09:23
        谢谢各位 (0) sunmoonstar_love 2005-07-20 21:11:20
      - 不用对点的编号排序？ (0) welkin_fafnir 2005-07-21 10:01:15
        我忘了算了，看来用个O(clogc)的就可以了。 (0) c0500448129 2005-07-21 10:34:47
        你实现了吗？有人用O(CLogC)的过了吗？它的点数不是无穷的啊，旋转有问题吧？很有可能0点周围的点是稀疏的啊？ (0) welkin_fafnir 2005-07-21 10:52:35
        Re:你实现了吗？有人用O(CLogC)的过了吗？它的点数不是无穷的啊，旋转有问题吧？很有可能0点周围的点是稀疏的啊？ (79) c0500448129 2005-07-21 11:02:20
        right.......... (2) welkin_fafnir 2005-07-21 11:10:08
        用基数排序之类的 (0) frkstyc 2005-07-21 11:26:06
        怎么弄？？只能哈希吧？还得用很强的哈希..........大的还要是大的..... (0) welkin_fafnir 2005-07-21 11:58:32
        我只知道这个是线性的，没写过也不想写 (0) frkstyc 2005-07-21 11:59:18
我的就是O(c^2logc)，挂的好惨 (0) scu05p07 2005-07-20 22:46:16
- 我在比赛中就用n^2log(n)过的，虽然慢但也没有tle啊！ (0) zhucheng 2005-07-20 23:09:29
  - 给VC的话的确会挂，傍晚的时候测过了 (77) frkstyc 2005-07-20 23:11:01
    - 548993 c0500448264 2500 Time Limit Exceed C 2.08K 2005-07-20 18:48:34 (81) frkstyc 2005-07-20 23:11:11
    - 还是g++好 (81) zhucheng 2005-07-21 11:46:18
  - 强悍啊，估计我写的有问题 (0) scu05p07 2005-07-21 13:00:14

Post your reply here:

Home Page Go Back To top