Jul 022010
 

Random Simple Polygon

Author: Ilham Winata Kurnia

This part of review is writen by the author himself (Ilham Winata Kurnia).

Given N collinear points, it is always possible to form a simple polygon using all the N points. Here we show two solutions (there are others) to solve this problem.

The first one is to pick one extreme point (e.g. the lowermost point) and sort the other points based on the angle formed by the segment connecting the extreme point and the other points and a horizontal segment going through the extreme point. Using the sorted points, we can obtain a parachute-like polygon.

The second way is to, first, create a bottom/top half convex hull from the points (other variation using left/right half is also possible), and then sort the remaining points by its x-coordinates. Join the remaining points appropriately to form the desired polygon.

Both of this solutions have O(N log N) implementations, which run well within the 1 second time limit. Due to the nice constraints, the only caution needed is when doing the arithmetics since the calculation does not fit into 32 bit integers.

This problem was solved by 13 teams. The first team to solve this problem: SYSU_Blover from Zhongsan (Sun Yat-sen) University, minute 34.


  16 Responses to “ACM-ICPC 2009 Jakarta – Problem Set & Analysis”

  1. Wah, akhirnya jadi juga :)) *Cepet* juga ya, ga perlu sampai satu tahun udah jadi =)) …

  2. Wogh.. siapa itu yang dihitamkan di YM yang lagi away?

    Btw, CONGRATS! Akhirnya jadi juga ini blog…

  3. Itu si husin, gw belum ganti nama di YM gw, jadi masih muncul ym-id dia. Diitemin biar ga diprotes ama orangnya πŸ˜€

  4. kyknya problem A ada yg lupa ditutup tagnya.

    ternyata write up H cuma gitu tok… πŸ˜› tau gitu harusnya bisa jadi dari dulu2 dong =))

  5. berhubung tampaknya komentarnya gak dibaca:
    Ax

  6. ah sial, tagnya gak bener.
    A x

  7. ah dodol ini
    < i > A < sub > x < sub > < /i >

  8. @mahli: ngapain lu?

  9. maaf, saya masih agak belum paham,
    himpunan S itu menyatakan himpunan apa ya?

    makasih sebelumnya..

  10. @akbar: yang soal Alien ya? S itu himpunan evil alien yang sudah dibom. Contoh: S = {0,1,1,0}, artinya ada 4 evil alien, alien kedua dan ketiga sudah dibom (0 = masih hidup, 1 = sudah dibom).

  11. @suhendry : saya sudah mulai paham,

    Dari yang saya tangkap:
    1. dp[i] : minimal bom untuk membunuh set i evil alien.
    2. dp[i] = min(dp[i], dp[i&(~v[j])]+1); untuk mengupdate apakah untuk membunuh minimal i alien diperlukan dp[i] bom, atau dp[i&(~v[j])] + 1 bom.

    Tapi masih ada yang saya belum mengerti mengenai:
    dp[i] = min(dp[i], dp[i&(~v[j])]+1);

    Misalkan di looping awal:
    – i = {0,0,0,1} = 1, dan dp[i] = 15;
    – ketika kita bom di koordinat j = (0,0), maka set evil yang akan mati = v[(0,0)] = {0,0,1,1} = 3.

    Jadi dp[1] = min(dp[1],dp[1&(~3)]+1)
    dp[1] = min(dp[1],dp[1&(12)]+1)
    dp[1] = min(dp[1],dp[12]+1).

    Tetapi 12 itu = {1,1,0,0} (artinya alien 1 dan 2 dari kiri mati)
    sehingga misalkan saja dp[12]+1 < dp[1], maka dp[1] = dp[12]+1 dan itu menjadi tidak valid karena dp[1] menyatakan set evil {0,0,0,1} atau alien keempat mati, sedangkan dp[12] hanya alien 1 dan 2 saja yang mati sedangkan alien 4 tidak.

    Kalau salah mohon dikoreksi..Maaf ya saya jadi banyak tanya…:D hehe

  12. horey…akhirnya….yg ditunggu-tunggu….sangat cepat nih…….:)

  13. Susu.. mana warnanyaaaaa? yang penjelasan gw…

  14. @felixh: huehehehehe, maaf, fixed πŸ˜€

  15. Problem E – A + B

    The smallest possible A + B can be obtained from A and B in their smallest possible number base. To find this you only need to find the smallest digit in A (and B) which is x and its smallest base is x + 1.

    bukannya yang bener gini ya?

    The smallest possible A + B can be obtained from A and B in their smallest possible number base. To find this you only need to find the LARGEST digit in A (and B) which is x and its smallest base is x + 1.

    CMIIW. thx

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)