Statistics

Problem Statement for "PointsInAPlane"

Problem Statement

You are given a collection of points in the plane, with x[i] and y[i] representing the i-th point. Return the number of triangles that can be formed using three of the points as vertices.

Definition

Class:
PointsInAPlane
Method:
howManyTriangles
Parameters:
int[], int[]
Returns:
int
Method signature:
int howManyTriangles(int[] x, int[] y)
(be sure your method is public)

Notes

  • Three points can only form a triangle if they are not colinear.

Constraints

  • x will contain between 1 and 50 elements, inclusive.
  • y will contain the same number of elements as x.
  • Each element of x will be between -1,000,000,000 and 1,000,000,000, inclusive.
  • Each element of y will be between -1,000,000,000 and 1,000,000,000, inclusive.
  • No two points will be at the same position.

Examples

  1. {0, 1, 2}

    {0, 1, 0}

    Returns: 1

    These three points for a triangle.

  2. {0, 1, 2}

    {0, 0, 0}

    Returns: 0

    These three points sit along the x-axis, and are all collinear.

  3. {0, 1, 2, 3}

    {0, 2, 1, 3}

    Returns: 4

    Pick any three points, and they form a triangle.

  4. {0, 1, 2, 1}

    {0, 0, 0, 1}

    Returns: 3

  5. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49}

    {0, 1, 2, 3, 10, 11, 12, 13, 14, 15, 16, 17, 18, 21, 22, 4, 5, 6, 7, 8, 9, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 19, 20, 49}

    Returns: 16880

  6. {0, 1}

    {0, 1}

    Returns: 0

  7. {-279528678,427247401,-328322123,323536710,196796774,-279401929,88298030,502508977,-463235597,-467358658,-263618514,-448695457,-115193184,494109703,-519359926,-131687475,-995674779,196796774,-295036026,196796774,-746310228,-879767149,-925942132,-369981222,444544431,394982328,443564649,346276781,-799225120,716668740,-111531169,344540560,87304510,326274445,874917917,-599518338,-280397059,229352405,444789167,8730450,-70912040,-658902248,874917917,86212309,569488855,329216151,874917917,-553131904,748463196,-116434147}

    {-247920576,600399732,-617421466,825180634,-962667378,330599666,168567080,-103406991,-272692121,483042178,565022018,693889042,-122710104,-103406991,-915609944,-470223043,-84234364,620651551,-314268506,335336928,93003755,-103406991,-915609944,-197440686,988640068,983209113,574643785,155449304,75332720,112571139,537894527,-747026172,166669120,334570832,881857426,-743007648,693889042,643377732,-501281407,166669120,-915609944,-507999993,-114896588,-570318564,693889042,350649531,-104866202,-284204754,867259023,883236755}

    Returns: 19594

  8. {-288349381,518998473,332292101,-221372051,530365969,100706249,444100934,495823917,-147765251,-913096454,188675250,764412726,948698950,-337580556,-187797048,-938171655,-545329894,112818524,-5441314,-754761958,615992108,-896725956,677704499,135915998,344128158,-941394709,630916838,-313757333,-514463071,-52776306,937229724,820177241,-250125097,-895349631,-673681495,-162824465,887891952,-142598278,-553430879,-259318474,-180966008,-79471427,839886882,113243535,132728457,-985050267,160905223,78273849,46952712,-129072435}

    {-750050346,-104077357,-400350832,-367619808,-188296752,-440679525,439137029,831734222,-215899920,-597144149,-450156834,-581613975,954949990,-735343269,898492173,-255839628,818971125,-499513337,-1008108,15503573,-132870048,620802469,-655478873,-817639789,-747344165,252383085,-828688028,-838192548,100612447,377342111,-486028782,631873797,-643454123,625129810,-4662746,-191007378,71399973,-208354954,-856389744,604177823,-519940767,-440452883,-190554740,-716641867,-48988929,893946239,234829788,102020890,-528599752,321158622}

    Returns: 19599

  9. {-640069080,198744754,593442645,791986916,243302342,-507598648,-19612480,-242775577,993126125,274592586,272682692,-23126360,-375982474,144066818,444954128,-101090097,235772741,534015318,-690412188,508578246,-320586667,-922143721,18384836,368403383,-507611754,-433609260,-432790345,69243981,978738806,-166847036,-883436695,-504524485,-77617668,-860465307,409213979,-289591792,-823735393,295755541,341666625,-710137033,203334287,-902114034,987335931,677926303,-396220921,-270016477,-212049606,669759284,-564977593,496196191}

    {343045871,-127783721,260630123,940429643,821292236,375307434,-56770703,19996020,684842853,975168874,419522905,16344115,-428262331,-409725788,-446273330,-231968913,673023061,-291277672,621103359,786322589,-69502078,-581421478,-519265728,-527748997,-655504888,699605378,282462505,-59591984,250060316,21704975,201712703,-310424329,724370266,307364460,-951497905,-627977234,488269997,-657815231,-54271457,-856716746,-328184185,100459016,199304526,495703284,-406392698,59527496,-513126730,477700630,388280609,294014571}

    Returns: 19599

  10. {-39802651,818370689,103826737,-297760259,-953556038,-296414620,318518572,584072372,818510713,-511773520,449532352,802083676,608778791,466372112,675963757,51389367,-5134089,-900669853,-331497419,-626126107,-313959133,247570609,357453544,125367579,-389704398,783324075,-180103150,583477911,-112213966,56182960,928644388,-952885951,592442043,820740766,551550564,20888756,444181018,267345149,748277788,784841820,-471367763,182672354,-707232560,56823018,-886504651,210294651,-610956907,111361520,392018096,-895073874}

    {-310130291,444747491,395016500,723077806,-356168590,-184393324,650880712,689391338,818054911,-141296446,-810174845,142295363,653999816,792967957,-923908486,876719868,696973261,-901919316,-774988207,40005908,773118385,697368169,-752569652,983206193,833949433,-373740994,645355376,964348953,-810174845,15869339,-90728215,970352448,-173134488,621545312,485991688,593498920,-132843546,-810174845,-895284494,361348443,483165920,842014324,-574869639,349510535,-865018805,992427256,-75953028,776769083,108802151,-469411969}

    Returns: 19598

  11. {-794900275,167311682,-600877411,416569369,28461500,817997008,490576066,-528940373,387023042,24809970,-941631562,817997008,387023042,387023042,-572775877,914422836,-334116949,520904611,-62385556,955459352,15086259,-600877411,817997008,-112565839,745011538,636979718,-600877411,668230992,574642723,-334040127,301618555,848472914,290032992,89911882,-570494980,62174936,-69453975,-963575968,120480537,-418891571,-915933853,-826101506,464214032,-893532426,-618061340,-975009569,-905414338,-305846250,133965,695336336}

    {677585008,770042495,508049962,-724302964,204455827,755794934,950409632,999789381,-65341140,51510292,28953647,243052372,-28499691,918910032,101193750,-997147712,-949830348,599633154,-239454464,995772305,-151393122,215089718,-803054538,956654313,-216718853,539961398,393968177,176146079,924259310,499729922,497659338,927267750,-482718243,323760844,-128573526,323760844,214694403,209761561,-367604592,-92862841,-750222906,643942977,-625538563,323760844,-655241468,13355135,-544270570,517426922,857331428,-855337814}

    Returns: 19596

  12. {422236621,535230032,484939336,922836766,813699549,914370731,-587033077,670204254,40065656,-806333922,394277710,733848004,-611440006,576445066,-255851124,-467536867,-751158165,34833144,-7114056,-670786343,-718306829,-160190873,-160190873,671779566,-43120504,483404423,-674668968,992745332,-43120504,-751521594,-160190873,576793691,-293342609,674627395,-466912478,535230032,313098632,-43120504,677892777,385410296,-171722064,293670861,-446112613,-486783999,-837408174,535230032,-469853033,-249716997,-434682541,-534963734}

    {-563553758,-362961599,-329280224,731293316,239120525,923469230,-647571489,-664237052,642312289,-204395973,-220235218,289036573,-647571489,-391571522,-962708191,-161452966,-455231433,-93295361,-12217344,-976552587,-857888850,171693658,134998523,278515377,-936640359,-307428374,414023569,-357528161,-488932994,280225000,-749449644,776407739,731293316,868198356,-236500385,-647571489,-829781335,252166560,-437845655,253561471,-293633944,-319210766,839891508,-165181733,570890102,-88718944,48988658,-968857185,325464266,-172197420}

    Returns: 19595

  13. {539386896,74263319,-897056086,-734805116,-512593910,55722718,490670824,-264823295,-946270328,-956674186,201726593,-478675024,901531052,-593652628,-94896426,-287056026,-392603738,-275276921,408504722,-750515403,-707587170,479635938,-377167790,841252423,622926929,757714792,-979663308,-666496561,704427261,767781952,191923011,715458428,891757664,-850472114,-609360058,8839951,-637334046,-724363836,-937076204,-344507642,-950655318,-418422867,747015864,-524605984,862559845,489756164,249754146,306924686,457169914,506746489}

    {-774247763,669313003,598270383,-379437999,-395298363,-243075852,115363021,-582655327,-387849449,-431951005,542559735,278324568,890597105,-795495939,504730656,-504269292,-803936716,194183425,17536097,-501152304,172628341,398504152,-762450744,345055492,517360881,-184368308,753946425,996827161,795938751,-787653191,-939309177,-17324565,-440007991,294607540,540993281,36193575,544478118,-970901749,122820825,663981795,61291880,387742693,897312283,-146550162,-272104082,612565971,-962862213,-768277993,-503039497,-937159799}

    Returns: 19600

  14. {426404313,-918066352,-278478783,-524141426,148809221,-418393564,754359164,118534621,-672284266,-367084900,296078048,662744025,-158282884,-674471834,-956085843,-78578355,-407347843,502699800,-500356516,25494647,999535443,558154658,-22003259,145953989,-129484887,129454179,512301108,-208056678,-353754291,-561514107,69180213,434396103,-632059929,-452205765,-339697673,-20529794,-789835076,-914937450,873893039,571908056,-359514560,61259877,-561514107,-896226772,-215982898,-184795193,766974815,316908974,940743476,-561514107}

    {626362269,-491479071,-547034263,478310260,-719402326,140446392,-199634324,-572870716,235659571,239660118,432047696,-948762884,42135916,720187914,-428071662,720187914,575960425,-893123669,-120778236,444346545,375139578,999441054,107344442,192488919,-190589235,261300932,978242209,114597187,-26119615,-64918213,101374977,720187914,-34467901,-472160269,-976245202,448493971,-449901164,920938471,-131248529,192488919,-548607495,291305840,-695337639,192488919,-611897388,-531053048,-909587141,761230301,999441054,942617629}

    Returns: 19595

  15. {212153995,124801251,-70814556,-676064450,739647213,-487459889,-880388999,148079555,-978715798,762072897,412558547,22202394,-587936310,-609381219,202378015,172730677,553023415,-379924602,816832369,-666570586,-14431783,829700196,-320051193,567528382,124145608,243369029,-233584157,-692370634,-191392014,-595798452,712018106,-610052061,9811106,-978715798,-769899060,-520906815,922123457,-376318940,-978715798,274960738,-673329956,-600554258,256315654,-759229465,53041478,-376318940,-376318940,-130591724,126230485,698456968}

    {830810380,-183734762,-897363114,592325954,-817458217,-920075783,8888002,-704074447,-744447130,-677857591,151882883,954909546,894198426,523591351,315860894,7186379,360670845,209673243,-409874578,896804167,-14971276,-291731926,900296847,-820624515,-857439660,252174947,-512391052,-939728888,169891705,34987018,-199655800,-576213682,505353733,-241059843,-895401694,-162991170,865268730,275872091,-320060531,-488233157,-788756705,59817674,598916054,-409874578,-281484050,-353059337,298442396,-306296124,130790071,-409874578}

    Returns: 19596

  16. {0, 1, 2, 3 }

    {0, 2, 1, 3 }

    Returns: 4

  17. {0, 1, 2 }

    {0, 1, 0 }

    Returns: 1

  18. {0, 1, 2, 1 }

    {0, 0, 0, 1 }

    Returns: 3

  19. {0, 1, 2 }

    {0, 0, 0 }

    Returns: 0

  20. {539 }

    {789 }

    Returns: 0

  21. {1, 2, 3 }

    {1, 2, 3 }

    Returns: 0

  22. {11111 }

    {134512345 }

    Returns: 0

  23. {5 }

    {66 }

    Returns: 0

  24. {0, 1, 2 }

    {0, 1, 2 }

    Returns: 0

  25. {0, -1, 2, 1 }

    {0, 0, 0, 1 }

    Returns: 3

  26. {0, -1000000000, 2 }

    {0, 743309312, 1000000000 }

    Returns: 1

  27. {1, 1, 2 }

    {2, 3, 4 }

    Returns: 1

  28. {715827882, 0, 715827872, 620384164, 4, 715827862, 715804791, 715827222, 38, 1116981, 715827878 }

    {715827882, 620384164, 4, 0, 715827872, 38, 1116981, 715827878, 715827862, 715804791, 715827222 }

    Returns: 165

  29. {0, 392, 40387 }

    {0, 28672, 1000000000 }

    Returns: 1

  30. {0, 999999900, 705032204, 1, 705032205, 999999901, 999999902, 2, 705032206, 999999903, 705032207, 3, 705032208, 4, 999999904, 705032209, 999999905, 5 }

    {0, 1, 5, 0, 5, 1, 1, 0, 5, 1, 5, 0, 5, 0, 1, 5, 1, 0 }

    Returns: 756

  31. {0, 131072, 131072, 131072, 0, 131072, 131072, 0, 131072 }

    {0, 0, 32768, 1, 1, 32769, 32770, 2, 2 }

    Returns: 63

  32. {0, 40000000, 80000000, 120000000 }

    {0, 40000000, 80000000, 120000000 }

    Returns: 0

  33. {0, 1, 2 }

    {1, 2, 3 }

    Returns: 0

  34. {0, 0, 1000000000 }

    {0, 536870912, 1000 }

    Returns: 1

  35. {0, 0, 536870912 }

    {0, 536870912, 1234 }

    Returns: 1

  36. {0, 40000000, 80000000 }

    {0, 40000000, 79999999 }

    Returns: 1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: