10135 - Herding Frosh

[junbin]

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

[little joey]

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]

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.

[junbin]

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]

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]

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]

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]

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

[BoCS]

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]

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]

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]

odd that I missed it thanks.

[Vexorian]

...
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]

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]

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.