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

不考虑点的位置，是不是当四边形为正方形时，面积最大？那么是不是追求近似正方形？

Posted by sunmoonstar_love at 2005-07-20 20:38:01 on Problem 2500
In Reply To:上限是O(c^2logc)，再高就不行了，最低应该是O(clogc)，O(logc)的写出来过不了 Posted by:frkstyc at 2005-07-20 18:29:08

Followed by:

这样子搞不行的 (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

Post your reply here:

Home Page Go Back To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator