10135 - Herding Frosh

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Tue Mar 09, 2004 2:18 am

horape wrote:I haven got AC yet, and have some discrepances with your data. As your datasets are so big I haven't given the effort needed to check the data. If you check it, please let me know what are the results.

Code: Select all

413.12  <- 410.59
  (0,0) (-10.4,37.2) (-29.6,46.22) (-35.91,37.27)
  (-40.11,13.37) (-46.58,-40.1) (-43.91,-46.68) (21.9,-49.2)
  (43.16,-46.62) (44.88,-7.59) (44.74,1.62) (41.18,42.98)
  (14.71,43.9) (4.37,34.5) (0.99,23.88) (0,0)

432.56  <- 430.86
  (0,0) (6.46,-1.65) (18.88,-4.59) (29.96,-5.41) (45.3,5.15)
  (44.12,15.25) (39.61,32.56) (31.68,43.5) (-8.42,49.99)
  (-46.24,44.41) (-49.4,-42.89) (-45.94,-49.96)
  (45.87,-49.36) (41.61,-30.82) (23.68,-9.91) (0,0)

430.20  <- 427.50
  (0,0) (-20.83,33.7) (-42.6,39.78) (-43.87,36.4)
  (-46.73,0.32) (-50.11,-46.2) (-27.91,-50.2) (42.2,-50.35) 
  (49.26,-45.53) (48.23,1.32) (43.18,24.87) (17.95,49.96)
  (-7.41,40.82) (-8.66,29.51) (0,0)

401.67  <- 392.03
 (0,0) (-6.7,29.77) (-10.25,36.46) (-11.43,36.86) 
 (-28.68,35.65) (-45.86,28.95) (-47.78,21.35) 
 (-50.11,-24.34) (-41.46,-42.94) (1.51,-47.88) 
 (32.13,-48.82) (44,-30.47) (45.45,19.69) (42.77,34.68)
 (26.6,48.12) (1.48,23.4) (0,0)


I managed to get AC with a lot of help from Per. :)

Anyway, the correct answers are:

Code: Select all

446.29

415.79

431.45

353.17

370.65

418.96

447.29

387.33

385.22

410.59

361.07

430.86

427.50

418.83

436.41

394.03

437.09

392.03

387.44

414.64

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Apr 22, 2006 1:29 pm

I get the same answers as above, which makes me believe that my algo is correct in principle, but I fail to get accepted :(
Can it be that rounding errors creap in? There is no special judge, but the range of the input values is not specified, so it can be anything in principle. On the other hand, there are enough people with accepted codes...

Can anyone verify a mega-big input file that is located here http://home.hccnet.nl/pj.wulff/megatest.zip? It's 5.4 Megs zipped, so be warned :)

I tried all the special cases I could think of (co-linearity and duplicate points mainly) but all seem to be handled correctly.

Thanks in advance.

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Fri Apr 28, 2006 6:21 am

little joey wrote:I get the same answers as above, which makes me believe that my algo is correct in principle, but I fail to get accepted :(
Can it be that rounding errors creap in? There is no special judge, but the range of the input values is not specified, so it can be anything in principle. On the other hand, there are enough people with accepted codes...

Can anyone verify a mega-big input file that is located here http://home.hccnet.nl/pj.wulff/megatest.zip? It's 5.4 Megs zipped, so be warned :)

I tried all the special cases I could think of (co-linearity and duplicate points mainly) but all seem to be handled correctly.

Thanks in advance.


My program generated quite a lot of differences from yours. I'll post my output as the next post.

Note that not all my programs are 100% correct. For some of them, they contain optimizations/floating point corrections that only work for the test data (one example is the choice of epsilon for floating point correction).

Anyway, I did this question too long ago to remember if this particular question had any floating point problems, etc. But if you want, I can send you the notes I wrote to myself as comments in the program.


ps: I'm not very much into competitive programming right now, so I don't watch threads anymore. If you reply, plesae send me a PM instead.
Last edited by junbin on Fri Apr 28, 2006 6:24 am, edited 1 time in total.

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Fri Apr 28, 2006 6:21 am

2036.90

2016.50

2024.43

1786.77

2035.76

2031.91

2047.72

1926.92

2017.60

2037.43

2009.28

2053.14

1976.60

2035.57

2040.49

2016.83

2016.51

1074.64

2033.82

2017.17

1991.99

2019.20

1953.64

2039.43

2050.24

2042.80

2031.43

2023.13

2015.69

1964.63

2043.51

2040.67

1912.34

1995.14

1975.53

2001.16

1969.98

2021.09

2021.97

1958.72

1804.00

2047.64

2037.63

2064.16

1983.02

2029.09

2037.32

1957.19

1918.07

2023.97

2019.95

2048.68

2056.02

2005.57

2035.24

1928.26

2028.65

2025.57

2034.12

1949.13

2032.70

2041.43

2022.75

2035.33

2019.39

1893.96

2013.36

1941.41

2031.15

1964.05

2011.78

2046.02

1808.25

2030.55

1957.50

2028.80

2020.65

1997.34

1869.82

2033.46

2006.19

2033.25

2050.38

1982.84

1961.95

2036.15

1997.04

2008.26

1866.93

2031.86

1549.58

2027.84

2051.17

2024.46

1810.60

1837.13

2013.33

1932.61

1752.39

2065.12

2045.59

1982.85

1984.43

1849.97

2052.88

2041.62

1746.36

1974.73

2052.30

1968.16

1954.16

2024.91

1939.48

2033.23

1948.56

2039.55

1899.45

867.14

1358.11

1893.69

2002.38

1881.92

1932.44

2028.38

1982.44

1960.18

1853.41

1988.15

1986.45

2020.11

2023.68

2060.59

1938.05

2037.72

1956.74

1981.01

1876.85

1938.23

2008.55

1863.31

2034.42

2045.25

2016.12

1955.39

2027.79

2033.05

2001.64

2067.02

2035.24

2052.01

1918.23

1503.21

1997.43

1938.53

1897.17

1934.10

2027.37

2044.59

2026.39

2040.36

1836.98

2044.35

2007.07

2016.23

2020.04

1997.22

2025.45

1115.78

1993.34

2004.56

1857.91

1905.20

2052.27

2054.60

2042.50

1871.50

1960.47

1866.80

2031.47

1975.98

2062.79

1933.73

1958.37

2019.42

1970.64

1954.87

2034.44

2005.50

2018.00

2004.86

1999.11

2024.40

2019.03

1701.79

1999.99

1774.10

1857.13

2007.84

1717.61

2028.58

1949.69

1776.99

1984.41

1880.31

2018.74

2002.71

2051.61

1936.43

1985.24

1826.49

355.63

2068.83

2049.10

1936.17

2010.13

2021.03

1551.12

2041.84

1995.90

1970.40

1977.96

1782.82

1860.74

1987.40

2037.91

1983.88

1954.10

2033.90

1025.07

2077.43

1974.07

2019.91

2058.22

2003.32

2010.14

1891.30

2022.41

1963.78

1999.45

2069.35

1995.25

1982.27

2047.46

1918.72

1998.29

1879.44

1741.71

2044.68

1951.63

1880.37

2036.35

1939.37

2030.05

1225.84

1995.44

2013.32

1779.30

1995.04

2032.04

1972.49

2052.91

1981.36

2024.93

1878.55

2020.57

1967.72

2013.91

1683.52

2004.97

1679.97

2035.20

2010.67

1253.50

1609.48

2014.40

2026.74

2017.39

2020.76

1999.86

1829.85

1551.38

1516.28

2027.29

2033.73

2043.99

2034.51

2012.34

2040.85

1996.50

1978.82

2006.14

2016.08

2032.86

1872.21

1949.38

1651.15

2004.45

1976.09

2026.96

2046.48

2052.03

1880.71

2016.70

1155.33

1998.46

1973.02

1788.09

2002.29

1989.19

1687.40

2072.58

2010.44

1980.23

2025.75

2038.95

1865.88

1812.08

1899.18

2043.82

2033.75

2007.24

2039.46

2048.08

1944.77

1957.13

2018.25

1970.39

1947.08

2033.51

1942.49

1944.64

1998.57

2023.00

2008.21

2040.98

1942.31

1948.85

1816.33

1950.88

1791.89

1839.12

2031.17

2013.23

1889.12

1947.31

2041.10

2041.97

2000.18

2019.73

2045.73

1815.37

2073.43

2021.93

1808.99

1924.78

2044.54

2029.48

1949.90

2026.59

1936.35

1830.34

1651.48

1988.92

1992.27

2030.06

2055.43

1957.68

1911.91

2036.73

2040.31

2056.96

2025.41

2061.46

2004.25

2024.59

1971.30

1997.10

1928.06

1962.37

1999.01

2068.91

2044.89

1961.78

1976.07

2044.35

2018.02

2056.88

1972.69

1904.61

1289.51

2018.36

1957.92

1972.25

1931.34

2001.35

1891.68

529.01

2022.95

2038.76

1990.97

1897.20

2040.71

1984.82

1812.00

1998.38

1847.52

1982.44

1954.60

2068.90

1320.81

2040.70

2019.99

2035.37

1635.81

2070.52

2057.68

1969.21

2026.04

1917.01

2048.41

1988.20

1967.46

2035.88

1992.78

2007.71

2004.19

2047.34

2010.30

1968.55

1999.41

2000.42

1997.93

1945.59

2051.32

1988.79

1980.32

2022.93

2009.27

2038.64

1981.82

963.65

1893.93

1923.80

2040.79

2028.57

2053.27

2045.57

2040.58

1998.79

1986.60

1992.48

1910.56

1917.30

2036.70

1969.16

1958.76

2032.03

2070.37

2033.69

2053.29

1989.91

2040.43

2050.08

2038.90

2000.25

1768.71

2007.06

2051.12

2064.94

2032.32

2017.53

1980.70

2020.63

2018.93

2022.31

1903.68

1959.31

2055.49

1923.53

1908.62

1690.42

2044.96

1930.17

2014.00

1959.15

2051.60

1886.88

2028.46

2040.85

2056.49

2004.57

2003.86

1919.07

2032.05

2016.76

2038.09

2035.57

1863.59

1923.58

1445.89

1966.68

1949.45

1978.04

2043.70

2021.40

2050.74

1672.42

2038.41

2039.01

1960.90

2011.85

1635.53

2051.44

2011.50

1964.54

2026.23

2041.11

2001.96

2052.55

1998.83

1948.26

1904.94

1988.93

1998.74

1943.65

2049.57

1734.29

2057.84

2011.93

1983.58

2043.02

2003.57

2016.15

2025.71

1991.75

2035.43

1927.35

1987.90

1824.13

1997.13

2050.03

1962.33

1958.99

1867.50

1922.97

2028.81

2046.54

1913.17

1966.30

1921.56

1957.23

2004.52

1786.35

2042.63

2045.29

2035.98

2030.01

2016.42

2008.64

2058.29

1928.22

1991.24

2013.71

2028.38

2026.79

2005.59

1971.13

1886.63

2037.32

2031.25

2034.31

1537.38

2039.61

2035.95

2039.18

2034.47

1929.32

1997.27

2036.10

2056.97

2015.57

1989.79

2051.52

2033.54

2038.64

2052.44

1897.66

2034.14

2021.14

2044.08

2024.22

1945.13

2003.66

2029.36

2012.89

5380.77

2019.31

1903.97

2034.70

2061.70

2031.43

1815.24

2021.64

2042.31

2029.73

1549.46

1911.95

2038.88

2021.30

2057.44

2047.28

1940.64

1902.31

1996.95

2026.19

2038.02

2035.28

2018.16

2017.20

2046.38

1952.91

2004.00

1349.34

1944.08

1998.01

1993.43

2041.90

1924.54

2050.21

2035.46

1780.93

2012.08

1899.43

2014.67

2005.79

1696.90

2030.28

2007.36

2010.86

1610.12

1809.10

1141.92

1955.85

1514.17

2062.44

1855.45

1961.20

2011.39

2023.24

1948.59

2033.86

1933.02

2014.51

2017.24

2008.82

1984.13

2025.30

1552.26

1744.90

2041.99

1955.91

1506.57

1774.67

1527.69

2027.46

2025.23

1971.22

2040.02

2016.18

1976.60

2017.95

1993.63

1948.69

1993.92

2057.56

2045.15

2010.42

1882.95

1994.26

2065.55

1911.23

1942.33

1861.13

976.05

2030.39

1975.10

2002.23

2050.93

2015.06

1995.95

1932.99

2058.99

1989.84

2017.60

2031.46

1992.69

2009.93

2023.98

2039.95

2016.51

1642.15

2014.82

2012.85

1974.08

1971.74

1888.22

1991.86

2056.86

1794.05

2050.80

2035.41

1891.52

2011.03

2049.37

1953.48

1987.65

1956.82

1985.24

2020.07

2050.04

2014.97

1999.66

2049.12

1858.89

2033.63

1985.83

2040.15

2019.61

2020.87

1992.08

1913.79

2026.06

1948.75

1997.43

2017.31

1971.99

2023.21

2049.85

1939.54

1912.77

1975.48

1930.15

1983.67

2039.85

2039.00

2054.53

2020.69

1847.69

2024.94

1955.11

1966.72

1986.94

1862.23

2010.01

1812.12

1992.62

2054.65

2059.97

1727.16

2019.48

1988.68

1998.16

1689.59

1980.25

1876.08

1722.08

1933.46

2072.54

2050.77

1952.98

2030.23

2019.53

2033.31

2044.99

2009.02

2030.74

2053.63

1499.65

1864.49

2028.23

1968.35

2042.06

2036.79

2042.15

2020.38

1846.97

1875.89

2005.29

1971.71

1961.26

2005.18

1967.71

2023.36

2030.86

2017.30

2012.33

2061.35

1991.52

2001.09

2022.23

1963.35

2028.79

1939.95

1809.66

1788.90

619.77

1950.40

2022.03

2002.94

2052.82

2029.89

1960.04

1974.20

2036.28

2063.40

1599.15

2061.37

2056.40

2011.36

1953.93

1995.46

1999.47

1962.63

2004.01

1910.10

2059.48

2058.41

1997.06

2022.56

2011.73

2026.25

2008.63

1970.86

2040.72

2028.36

1227.25

2050.33

1976.12

2026.75

2040.44

2002.30

1941.57

1986.28

2038.67

1862.04

2022.97

2072.45

1891.81

1964.84

1970.09

1820.23

1995.34

2032.90

2041.58

2029.08

1911.13

2004.91

1832.80

2038.77

5270.17

1802.88

1991.72

2015.02

1985.46

2000.16

1992.48

1791.98

2036.53

1977.14

2003.40

2004.20

2071.59

1814.35

2033.26

2033.02

1628.56

2034.04

1924.24

2034.14

1973.99

1935.56

2048.74

1608.57

1999.29

2049.25

1567.53

2007.75

1779.10

2063.64

2061.97

1239.39

2021.56

2019.90

2061.05

1967.28

1959.78

1973.18

1781.75

1974.15

2024.29

2057.93

1961.62

1958.55

1901.50

1854.53

2024.99

2005.55

1932.90

1813.19

1577.51

1956.09

1814.82

1992.83

1734.88

1961.75

2022.71

2041.53

2034.34

2048.14

1964.77

1863.76

1927.75

1979.04

2014.13

2039.77

2038.77

1967.83

1963.79

1654.18

1911.38

2003.80

1900.35

2010.46

1695.21

1993.45

1624.57

1975.66

1995.02

1891.04

1947.41

1852.76

2046.01

2018.43

2011.06

1958.92

1834.46

2001.11

2050.17

2072.67

1974.33

2007.93

2012.42

2002.51

1957.95

1956.98

1875.79

1878.31

1990.25

2021.22

1990.93

1935.38

1963.14

2029.23

1994.07

2029.15

2028.05

1638.39

2045.47

2040.74

1995.58

2020.46

1989.12

2050.72

2034.93

1985.45

1996.86

1984.02

2028.32

1821.72

1965.81

2031.48

2009.13

1880.90

2033.28

2029.82

1650.17

2020.80

2024.54

1993.64

2015.12

2021.84

1876.60

2056.56

1946.52

2047.44

2020.03

1967.06

1963.41

2031.18

1998.77

mrbobguy
New poster
Posts: 3
Joined: Tue May 02, 2006 2:14 am

10135

Post by mrbobguy » Fri Sep 15, 2006 5:07 am

OK. I've looked at previous discussion of this problem, but none help me.

I see that convex hull does not quite give the answer to this problem. I was wondering, what method does give the right answer quick enough?

Does this method use the convex hull as part of it? (I would think that it would...in this case, how do you account for the "telephone pole" at the origin?)

I saw discussion of computing partial convex hulls with sets of points within triangles formed by origin and hull points. Is this how to get the answer? And if so, could someone explain this to me in more detail?

I have tried different things, but nothing I can think of would work fast enough. Any help would be appreciated.

mrbobguy
New poster
Posts: 3
Joined: Tue May 02, 2006 2:14 am

Nevermind...

Post by mrbobguy » Sun Sep 17, 2006 11:28 pm

Nevermind. I figured it out.

Wow this is a really nice problem. It takes a REALLY good understanding of convex hull and the algorithm behind it to figure it out. I didn't have a really good understanding before, but thanks to this problem, I think I can safely say that I do now.

For those who like geometry, check this problem out if you haven't already. It's a tough but good one.

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Post by mukeshtiwari » Tue Nov 21, 2006 8:57 pm

hi i try to solve this problem by convex hull but it's not giving me correct answer .will u explain the problems ...i could not understand the problem but got some idea from problem 681 . i think we have to calculate contour points.....on polygon.....plz explain...i tried this problem many times...

BoCS
New poster
Posts: 3
Joined: Sun Feb 04, 2007 8:24 am

Post by BoCS » Sun Feb 04, 2007 8:47 am

How did you end up dealing with the origin point? I mean, how do you choose the two points the origin connects to?

BoCS
New poster
Posts: 3
Joined: Sun Feb 04, 2007 8:24 am

Post by BoCS » Tue Feb 06, 2007 3:46 am

I've been working on this problem too, and I think I'm running into the same problem as you were. I can't figure out an efficient way to add the origin to the hull (the posted code didn't appear to be adding it correctly, since it went straight from two points on the hull to the origin without making sure the hull is still convex.)

Any suggestions?

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian » Tue Feb 20, 2007 3:18 am

Per wrote:Hi!

Figuring out the answer to your question has now taken me roughly an hour (though the answer is quite simple). Good question. :)

The problem with your algorithm is that your choice of M is not necessarily the optimal choice. For instance, if the origin is very close to v_i, it is better to put M nearer v_i.

For instance, for the case

Code: Select all

7
1 1
-9 1
-9 -9
1 -9
1 -2
1 -4
-3 0.9
Your algorithm (or at least my implementation of it), will answer 42.65, whereas the correct answer is 42.55.
My answer is 40.55, and I think it is correct, afterall it is the best way to enclose all the frosh using the least perimeter, I am not sure if you meant 40.55 (notice the similarity) or that my alg is not really right although I really think the correct solution is 40.55.

Edit:

Hey, even the sample i/o is wrong then?

My new algorithm is generating this (for original input):

Code: Select all

 __
| /
|_\
(there 's a complete line bellow the | \ , I was not able to enter some characters, the forum software cut them)

It is covering the frosh and it goes through 0,0 so what's wrong? The output is 8.83.

So, is there something I am missing?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Feb 20, 2007 3:04 pm

My answer is 40.55, and I think it is correct, afterall it is the best way to enclose all the frosh using the least perimeter,
Yes, but that's not exactly what the problem is asking for :)
The senior classman used the minimum amount of silk necessary to encircle all the frosh plus one extra metre at each end to tie it.

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian » Tue Feb 20, 2007 4:14 pm

odd that I missed it thanks.

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian » Tue Feb 20, 2007 4:21 pm

...
Now I got WA, anyone got more test cases? The sample one and the one posted here are correct for my algorithm

Edit: I found a lot of i/o that is wrong, nevermind.

BoCS
New poster
Posts: 3
Joined: Sun Feb 04, 2007 8:24 am

Post by BoCS » Thu Feb 22, 2007 7:23 am

I've been having some problems with this program. Here is what I have so far, which gets a runtime error due to invalid memory reference (hopefully it will help some of you out too):

Code: Select all

#include<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

// very small constant
static const double EPSILON = 0.00001;
static const bool TRACE = false;

class Point
{
public:
    double x, y;
    
    // default constructor
    Point() {}
    
    // explicit value constructor for convenience
    Point(const double inX, const double inY)
    {
        x = inX;
        y = inY;
    }
    
    // overloaded == operator
    bool operator==(const Point &p) const
    {
        return (x == p.x && y == p.y);
    }
    
    // overloaded != operator
    bool operator!=(const Point &p) const
    {
        return (x != p.x || y != p.y);
    }
};



// ewwwwww...global variable!
Point firstPoint;

// computes a convex hull
// NOTE: first point is duplicated at the end
void convexHull(vector<Point> &in, vector<Point> &hull);

// returns true if p2 is to the left of the ray between firstPoint and p1
// used to sort the points
bool smallerAngle(const Point &p1, const Point & p2);

// used for debugging only
void printVector(const vector<Point> &v);

// returns the perimeter of a convex hull
// NOTE: push the first point to the end of the vector first
double polyPerimeter(const vector<Point> &in);

// returns the distance between two points
double pointDistance(const Point &a, const Point &b);

// returns true if a is to the left of b
// uses y position as a tiebreaker
// used to sort the points
bool leftLower(const Point &a, const Point &b);

// result is positive if p is to the left of the ray from r1 to r2
// negative if p is to the right
// 0 if they are collinear
double triangleArea(const Point &r1, const Point &r2, const Point &p);

// returns 1 if p is to the left of the ray from r1 to r2
// returns -1 if p is to the right
// returns 0 if they are collinear
int compare(const Point &r1, const Point &r2, const Point &p);

int main()
{
    int numCases, numFrosh, beginSubs, endSubs;
    double tempDist, minDistance, perimeter, fX, fY;
    Point origin(0,0);
    vector<Point> in, hull;
    
    // input number of cases
    cin >> numCases;
    
    for(int c = 0; c < numCases; c++)
    {
        // input frosh
        cin >> numFrosh;
        in.clear();
        in.push_back(origin); // adding the origin
        
        for(int f = 0; f < numFrosh; f++)
        {
            cin >> fX >> fY;
            in.push_back(Point(fX, fY));
        }
        
        // compute hull
        convexHull(in, hull);
        in.push_back(in[0]); // wraparound condition breaks otherwise
        
        perimeter = polyPerimeter(hull);
        
        // if the origin is not part of the hull
        if(find(hull.begin(), hull.end(), origin) == hull.end())
        {
            // sort around the origin
            firstPoint = origin;
            sort(in.begin(), in.end(), smallerAngle);
            
            minDistance = perimeter; // Some large value
            
            beginSubs = 0;
            endSubs = 0;
            
            for(unsigned int i = 0; i < hull.size() - 1; i++)
            {
                // begin subs and end subs determine the portion of the hull being investigated
                while(in[beginSubs] != hull[i])
                    beginSubs++;
                
                while(in[endSubs] != hull[i+1])
                    endSubs++;
                
                // step through one triangle of the hull
                for(int j = beginSubs; j < endSubs; j++)
                {
                    // subtract the side of the hull and two segments which will be counted twice
                    tempDist = -( pointDistance(hull[i], hull[i+1]) + 
                        pointDistance(hull[i], origin) + 
                        pointDistance(hull[i+1], origin) );
                    
                    // copy from beginSubs to j and push_back origin
                    vector<Point> temp(j-beginSubs+1);
                    vector<Point> partHull;
                    copy(in.begin()+beginSubs, in.begin()+j+1, temp.begin());
                    temp.push_back(origin);
                    
                    // compute its hull
                    convexHull(temp, partHull);
                    tempDist += polyPerimeter(partHull);
                    
                    if(TRACE)
                    {
                        cout << "The first partial hull is:\n";
                        printVector(partHull);
                    }
                    
                    // copy from j+1 to endSubs and push_back origin
                    temp.resize(endSubs - j);
                    copy(in.begin()+j+1, in.begin()+endSubs+1, temp.begin());
                    temp.push_back(origin);
                    
                    // compute its hull
                    convexHull(temp, partHull);
                    tempDist += polyPerimeter(partHull);
                    
                    if(TRACE)
                    {
                        cout << "The second partial hull is:\n";
                        printVector(partHull);
                    }
                    
                    if(tempDist < minDistance)
                        minDistance = tempDist;
                    
                    if(TRACE)
                        cout << "The total distance is " << tempDist << endl << endl;
                }
            }
        }
        else
            minDistance = 0;
        
        if(TRACE)
        {
            cout << "HULL:\n";
            printVector(hull);
            cout << "MIN DISTANCE: " << minDistance << endl;
        }
        
        cout << setprecision(2) << minDistance + perimeter + 2 << endl;
    }
    return 0;
}

void convexHull(vector<Point> &in, vector<Point> &hull)
{
    int top = 1;
    unsigned int i;
    
    // sort by leftLower
    sort(in.begin(), in.end(), leftLower);
    
    // erase duplicates
    in.erase(unique(in.begin(), in.end()), in.end());
    hull.resize(in.size()+1);
    unsigned int n = (unsigned int)in.size();
    
    // pick lowest leftmost point
    firstPoint = in[0];
    
    // all points are on hull
    if(n <= 3)
    {
        for(i = 0; i < in.size(); i++)
            hull[i] = in[i];
        
        hull[n] = hull[0];
        
        return;
    }
    
    // sort by angle around firstPoint
    sort(in.begin()+1, in.end(), smallerAngle);
    hull[0] = in[0];
    hull[1] = in[1];
    
    in.push_back(firstPoint); // wraparound
    i = 2;
    
    // build hull
    while(i <= n)
    {
        if(compare(hull[top-1], hull[top], in[i]) <= 0)
            top--;
        else
        {
            top++;
            hull[top] = in[i];
            i++;
        }
    }
    
    in.pop_back();
    hull.resize(top);
    hull.push_back(hull[0]); // hull wraps around
}

bool smallerAngle(const Point &p1, const Point & p2)
{
    if(compare(firstPoint, p1, p2) == 0) // collinear
    {
        if(pointDistance(firstPoint, p1) <= pointDistance(firstPoint, p2))
            return true;
        else
            return false;
    }
    
    if(compare(firstPoint, p1, p2) > 0)
        return true;
    else
        return false;
}

void printVector(const vector<Point> &v)
{
    for(unsigned int i = 0; i < v.size(); i++)
        cout << v[i].x << ' ' << v[i].y << endl;
}

double polyPerimeter(const vector<Point> &v)
{
    double d = 0;
    
    for(unsigned int i = 0; i < v.size() - 1; i++)
        d += pointDistance(v[i], v[i+1]);
    
    return d;
}

double pointDistance(const Point &a, const Point &b)
{
    return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

bool leftLower(const Point &a, const Point &b)
{
    if(a.x < b.x) return true;
    if(a.x > b.x) return false;
    
    if(a.y < b.y) return true;
    if(a.y > b.y) return false;
    
    return false;
}

double triangleArea(const Point &r1, const Point &r2, const Point &p)
{
    return (r1.x * r2.y - r1.y * r2.x + r1.y * p.x - 
        r1.x * p.y + r2.x * p.y - p.x * r2.y) / 2.0;
}

int compare(const Point &r1, const Point &r2, const Point &p)
{
    if(triangleArea(r1, r2, p) > EPSILON)
        return 1;
    else if(triangleArea(r1, r2, p) < -EPSILON)
        return -1;
    else
        return 0;
}

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Post by DJWS » Thu May 29, 2008 11:15 am

My algorithm is just wrapping all points in angular sequence, and try to enumerate all possible starting positions.
The code is judged as WA. I wonder if it has any mistakes.

Code: Select all

Cut After AC.
Last edited by DJWS on Sun Jan 16, 2011 8:01 am, edited 3 times in total.

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest