# 查看完整版本 : 火雞

tom.care 2018-11-29 01:03 PM

## 火雞

*** 作者被禁止或刪除 內容自動屏蔽 ***

tom.care 2018-12-17 05:48 AM

*** 作者被禁止或刪除 內容自動屏蔽 ***

Erect the Fence  :fst_010:

darigold 2018-12-18 11:36 AM

[code]    class Solution
{
public:
vector<Point> outerTrees(vector<Point>& points)
{
if (points.size() < 4)
{
return points;
}
for (int i = 1; i < points.size(); i++)
{
if (points[i].x < points[0].x || (points[i].x == points[0].x) && (points[i].y < points[0].y)) {
swap(points[i], points[0]);
}
}

while (true)
{
// In the first iteration, we know that it is impossible for the hull to end, so we pick index 1 as the candidate and start the loop from 2
// In any other iterations, it is possible that the convex hull ends, so we use 0 as the nextIndex and loop through all the points that are not on the hull
int nextIndex = (answer.size() == 1) ? 1 : 0;
int start = answer.size() + nextIndex;

for (int testIndex = start; testIndex < points.size(); testIndex++)
{
Point& nextPoint = points[nextIndex];
Point& testPoint = points[testIndex];
bool take = false;
int cross = (nextPoint.x - basePoint.x) * (testPoint.y - basePoint.y) - (nextPoint.y - basePoint.y) * (testPoint.x - basePoint.x);
if (cross > 0)
{
take = true;
}
else if (cross == 0)
{
// If we found co-linear points in the set of points that are not added to the hull, they are either all added to the hull or not at all.
// so we picked the one with least distance to keep it in the hull order.
//
// The statement above is always true, but the co-linear points we just found might not all come from the points not added to the hull.
// The only special case when nextIndex = 0. In that case, we should always set take = true to ensure this point (and any other points
// also co-linear with points[0]) to be chosen in the hull.
int next_base_squared_dist = (nextPoint.x - basePoint.x) * (nextPoint.x - basePoint.x) + (nextPoint.y - basePoint.y) * (nextPoint.y - basePoint.y);
int test_base_squared_dist = (testPoint.x - basePoint.x) * (testPoint.x - basePoint.x) + (testPoint.y - basePoint.y) * (testPoint.y - basePoint.y);
if (nextIndex == 0 || next_base_squared_dist > test_base_squared_dist)
{
take = true;
}
}
if (take)
{
nextIndex = testIndex;
}
}
if (nextIndex == 0)
{
break;
}
}

}
};
};[/code]

tom.care 2018-12-18 03:55 PM

*** 作者被禁止或刪除 內容自動屏蔽 ***

[quote]原帖由 [i]tom.care[/i] 於 2018-11-29 01:03 PM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=491249914&ptid=27880325][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]
[url=https://leetcode.com/problems/erect-the-fence/]https://leetcode.com/problems/erect-the-fence/[/url] [/quote]
Tom.care

Please PM if you are interested.

[quote]原帖由 [i]tom.care[/i] 於 2018-12-18 03:55 PM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=492155900&ptid=27880325][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]

9120744 [/quote]食雞係好殘忍架！:fst_004:你無睇 Peta 既咩？:fst_016:

assembly.jc 2018-12-20 03:10 AM

import Data.List (sortBy)

data Orientation = Coliner | Clockwise | CounterClock deriving (Show, Eq)

distance (x1, y1) (x2, y2) = (x1 - x2) ^ 2 + (y1 - y2) ^ 2

orientation (px, py) (qx, qy) (rx, ry) =
case (qy - py) * (rx - qx) - (qx - px) * (ry - qy)
of x | x == 0    -> Coliner
| x >  0    -> Clockwise
| otherwise -> CounterClock

orientOrder p0 p1 p2 =
case orientation p0 p1 p2 of
Clockwise    -> GT
CounterClock -> LT
Coliner      -> if distance p0 p1 >= distance p0 p2 then GT else LT

findLowestPoint points =
head \$ filterPoint leftmost \$ filterPoint lowest points
where lowest   ps p    = minimum (map snd ps) == snd p
leftmost ps p    = minimum (map fst ps) == fst p
filterPoint f ps = filter (f ps) ps

findConves stack [] = stack
findConves stack@(c:p:_) points@(n:ps)
| orientation p c n == Clockwise = findConves (tail stack) points
| otherwise                      = findConves (n:stack) ps

convexHull points =
let orderedPoints = p0 : sortBy (orientOrder p0) (filter (/=p0) points)
in  findConves (reverse \$ take 3 orderedPoints) (drop 3 orderedPoints)
where p0 = findLowestPoint points

main = mapM_ print \$ convexHull [(1,1), (2,2), (2,0), (2,4), (3,3), (4,2)]

[[i] 本帖最後由 assembly.jc 於 2018-12-20 03:22 AM 編輯 [/i]]

[quote]原帖由 [i]獵頭先生[/i] 於 2018-12-18 04:00 PM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=492156138&ptid=27880325][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]

Tom.care

Please PM if you are interested. [/quote]

tom.care 2018-12-21 08:14 AM

*** 作者被禁止或刪除 內容自動屏蔽 ***

assembly.jc 2018-12-22 01:34 PM

[quote]原帖由 [i]tom.care[/i] 於 2018-12-21 08:14 AM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=492273719&ptid=27880325][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]
[url=https://leetcode.com/problems/numbers-at-most-n-given-digit-set/]https://leetcode.com/problems/numbers-at-most-n-given-digit-set/[/url] [/quote]

countLessThan num digits =
let nums = map (read . pure) (show num)::[Int]
ds   = map (read . pure) digits::[Int]
in  count nums ds + sum [length ds ^ k | k <- [1..length nums-1]]
where count [] _      = 1
count (n:ns) ds = length (filter (<n) ds)  * length ds ^ length ns +
length (filter (==n) ds) * count ns ds

main = do print \$ countLessThan 100 "1357"
print \$ countLessThan 1000000000 "149"

tom.care 2018-12-25 11:32 AM

*** 作者被禁止或刪除 內容自動屏蔽 ***

darigold 2018-12-27 04:55 AM

[quote]原帖由 [i]assembly.jc[/i] 於 2018-12-20 03:10 AM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=492224903&ptid=27880325][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]

[/quote]

(0,0)。[code]main = mapM_ print \$ convexHull [(0,0), (1,1), (2,2), (3,3), (4,4), (0, 1), (0, 2), (0, 3), (0, 4)][/code][attach]9151106[/attach]

[url]https://leetcode.com/problems/erect-the-fence/discuss/103307/c-graham-scanmonotone-chain-dealing-with-collinear-cases[/url]

assembly.jc 2018-12-27 05:27 PM

[quote]原帖由 [i]darigold[/i] 於 2018-12-27 04:55 AM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=492523506&ptid=27880325][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]

(0,0)。main = mapM_ print \$ convexHull [(0,0), (1,1), (2,2), (3,3), (4,4), (0, 1), (0, 2), (0, 3), (0 ... [/quote]

Graham Scan 已經搵晒 d vertices 出來，只要將這些 vertices 連線就係多邊形嘅邊界，再將係邊界上的 points 加入答案就可以了。

[[i] 本帖最後由 assembly.jc 於 2018-12-27 05:37 PM 編輯 [/i]]

tom.care 2018-12-29 01:21 AM

*** 作者被禁止或刪除 內容自動屏蔽 ***

assembly.jc 2018-12-29 03:27 AM

[quote]原帖由 [i]darigold[/i] 於 2018-12-27 04:55 AM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=492523506&ptid=27880325][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]

(0,0)。main = mapM_ print \$ convexHull [(0,0), (1,1), (2,2), (3,3), (4,4), (0, 1), (0, 2), (0, 3), (0 ... [/quote]

findBoundary _ [] _ = []
findBoundary _ _ [] = []
findBoundary p0 points vs = filter onBoundary points
where onBoundary p= any (isInterior p) (zip vs (tail vs) ++ [(last vs, p0)])
isInterior p (sp, ep) = (p /= sp && p /= ep) &&
(orientation sp p ep == Coliner) &&
(orientOrder sp p ep == LT)

convexHull points =
let orderedPoints = p0 : sortBy (orientOrder p0) (filter (/=p0) points)
conves        = reverse \$ findConves (reverse \$ take 3 orderedPoints)
(drop 3 orderedPoints)
boundPoints   = findBoundary p0 points conves
in  nub (conves ++ boundPoints)
where p0 = findLowestPoint points

[quote]原帖由 [i]獵頭先生[/i] 於 2018-12-20 11:18 AM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=492235884&ptid=27880325][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]

tom.care 2019-2-9 08:49 AM

*** 作者被禁止或刪除 內容自動屏蔽 ***

darigold 2019-2-14 10:13 AM

[quote]原帖由 [i]tom.care[/i] 於 2018-12-29 01:21 AM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=492607614&ptid=27880325][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]
[url=https://leetcode.com/problems/delete-columns-to-make-sorted/]https://leetcode.com/problems/delete-columns-to-make-sorted/[/url] [/quote][quote]class Solution
{
public:
int minDeletionSize(vector& A)
{
if (A.size() == 0)
{
return 0;
}
int l = A[0].length();
int ans = 0;
for (int c = 0; c < l; c++)
{
for (int r = 1; r < A.size(); r++)
{
if (A[r][c] < A[r - 1][c])
{
ans++;
break;
}
}
}
return ans;
}
};[/quote]

[[i] 本帖最後由 darigold 於 2019-7-30 09:38 PM 編輯 [/i]]

alvin__luk 2019-2-14 12:37 PM

Interesting...

I actually implemented this function in one of my computer vision libraries many years ago.

tom.care 2019-2-14 11:43 PM

*** 作者被禁止或刪除 內容自動屏蔽 ***