Statistics

Problem Statement for "ConvexPolygons"

Problem Statement

You are given two polygons, described by two String[]s polygon1 and polygon2. The elements of polygonx (x=1 or 2) consist of two space separated integers describing the coordinates of the vertices of polygon x in counterclockwise order.

Both polygons will be convex and have non-zero areas. Furthermore the two polygons will be such that a vertex of one polygon won't lie on the sides of the other.

Return the area of the overlap of the two polygons.

Definition

Class:
ConvexPolygons
Method:
overlap
Parameters:
String[], String[]
Returns:
double
Method signature:
double overlap(String[] polygon1, String[] polygon2)
(be sure your method is public)

Notes

  • A polygon being convex means: every straight line joining any two interior points of the polygon is entirely contained in the interior of the polygon.
  • A return value with either an absolute or relative error of less than 1e-9 is considered correct.

Constraints

  • polygon1 and polygon2 each have between 3 and 50 elements, inclusive.
  • Each element of polygon1 and polygon2 has length between 1 and 50, inclusive.
  • Each element of polygon1 and polygon2 consists of two space separated integers with values between -1000 and 1000, inclusive.
  • Both polygons will be convex and have non-zero areas.
  • Both polygons will be such that a vertex of one polygon won't lie on the sides of the other.
  • The points described by polygon1 and polygon2 will be in counterclockwise order.

Examples

  1. {"00 00","02 00","00 03"}

    {"1 1","3 1","3 3", "1 3"}

    Returns: 0.08333333333333326

  2. {"-1 -1","1 -1","1 1","-1 1"}

    {"-2 -2","0 -2","2 -2","2 0","2 2","0 2","-2 2","-2 0"}

    Returns: 4.0

    When one polygon encloses the other, the overlap is the area of the smaller one.

  3. {"-1 -1","-2 -1","-1 -2"}

    {"1 1","2 1","1 2"}

    Returns: 0.0

    They don't overlap.

  4. {"-2 0","-1 -2","1 -2","2 0","1 2","-1 2"}

    {"0 -3","1 -1","2 2","-1 0"}

    Returns: 5.233333333333333

  5. {"999 -1000","1000 -1000","999 1000"}

    {"-1000 1000","-1000 999","1000 999"}

    Returns: 2.498272806406021E-7

  6. {"-2 -2","2 -2","2 2","-2 2"}

    {"3 1","10 1","10 2"}

    Returns: 0.0

  7. {"0 0","10 9","9 10"}

    {"0 4","-10 0","-9 -10","13 -7","14 1"}

    Returns: 1.1435590357746053

  8. {"-1 -1","1 -1","1 1","-1 1"}

    {"0 0","1000 -1","1000 1"}

    Returns: 9.999999999999436E-4

  9. {"1000 0","992 125","968 248","929 368","876 481","809 587","728 684","637 770","535 844","425 904","309 951","187 982","62 998","-62 998","-187 982","-309 951","-425 904","-535 844","-637 770","-728 684","-809 587","-876 481","-929 368","-968 248","-992 125","-1000 0","-992 -125","-968 -248","-929 -368","-876 -481","-809 -587","-728 -684","-637 -770","-535 -844","-425 -904","-309 -951","-187 -982","-62 -998","62 -998","187 -982","309 -951","425 -904","535 -844","637 -770","728 -684","809 -587","876 -481","929 -368","968 -248","992 -125"}

    {"998 62","982 187","951 309","904 425","844 535","770 637","684 728","587 809","481 876","368 929","248 968","125 992","0 1000","-125 992","-248 968","-368 929","-481 876","-587 809","-684 728","-770 637","-844 535","-904 425","-951 309","-982 187","-998 62","-998 -62","-982 -187","-951 -309","-904 -425","-844 -535","-770 -637","-684 -728","-587 -809","-481 -876","-368 -929","-248 -968","-125 -992","0 -1000","125 -992","248 -968","368 -929","481 -876","587 -809","684 -728","770 -637","844 -535","904 -425","951 -309","982 -187","998 -62"}

    Returns: 3126769.6289103786

  10. {"-1000 -999","999 -999","999 1000","-1000 1000"}

    {"-999 -1000","1000 -1000","1000 999","-999 999"}

    Returns: 3992004.0

  11. {"67 789","-34 -974","23 -847"}

    {"954 54","-876 456","-634 -4"}

    Returns: 4623.942657081756

  12. {"-910 -40","868 -49","993 -5","949 5","792 28","-245 44","-950 49","-936 11"}

    {"97 -264","89 341","63 393","-45 422","-92 -95","-83 -474","1 -491","66 -492","96 -290"}

    Returns: 15008.12699970091

  13. {"991 404","995 523","857 732","-75 748","-794 739","-953 527","-976 460","-984 320","-899 259","-234 258","355 262","837 278"}

    {"-45 -260","-963 -254","-986 -274","-995 -339","-971 -585","-965 -608","-893 -748","-211 -747","-39 -745","925 -709","957 -306","802 -268"}

    Returns: 0.0

  14. {"-1000 1000","-1000 -999","999 1000"}

    {"1000 -1000","1000 999","-999 -1000"}

    Returns: 0.0

  15. {"988 970","355 999","-299 999","-928 962","-963 933","-982 795","-987 723","-998 -35","-1000 -223","-999 -490","-996 -562","-989 -688","-960 -882","-909 -965","-635 -1000","498 -998","883 -978","985 -858","997 -452","997 528","997 650"}

    {"99 -69","99 -47","99 -40","99 51","97 89","92 99","85 99","37 99","36 99","33 99","0 99","-40 99","-91 97","-98 75","-100 14","-100 -4","-100 -23","-98 -86","-97 -89","-92 -95","-89 -97","-66 -100","-60 -100","-59 -100","-48 -100","-2 -100","9 -100","75 -100","84 -100","99 -96"}

    Returns: 39047.0

  16. {"-15 -9","-36 -4","-21 -21"}

    {"999 535","997 948","986 994","953 999","941 999","801 999","647 999","142 999","-828 999","-900 999","-991 974","-999 971","-1000 771","-1000 607","-1000 -264","-1000 -358","-1000 -663","-1000 -669","-1000 -972","-989 -992","-986 -995","-838 -998","-651 -999","485 -1000","949 -1000","954 -1000","990 -989","992 -959","999 -676","999 -667","999 -457","999 -251","999 -237","999 6","999 157","999 218"}

    Returns: 141.0

  17. {"-900 220","-900 4","-899 -190","-897 -324","-888 -399","-671 -400","-440 -400","55 -400","87 -388","97 -371","99 -329","99 168","99 287","98 415","95 584","55 595","43 596","-69 599","-74 599","-160 599","-358 599","-632 599","-689 599","-815 598","-888 596","-895 525","-897 467","-898 406"}

    {"899 538","892 597","659 599","530 599","525 599","423 599","-35 599","-70 596","-89 575","-91 571","-99 458","-100 381","-100 326","-100 132","-100 22","-100 -28","-100 -247","-100 -279","-99 -360","-81 -387","16 -397","77 -398","356 -400","394 -400","659 -400","704 -400","737 -399","885 -391","899 -379","899 -150","899 -50","899 -41"}

    Returns: 194517.64408590665

  18. {"499 31","491 93","475 154","452 212","422 267","385 318","342 364","293 404","240 438","184 464","124 484","62 496","0 500","-62 496","-124 484","-184 464","-240 438","-293 404","-342 364","-385 318","-422 267","-452 212","-475 154","-491 93","-499 31","-499 -31","-491 -93","-475 -154","-452 -212","-422 -267","-385 -318","-342 -364","-293 -404","-240 -438","-184 -464","-124 -484","-62 -496","0 -500","62 -496","124 -484","184 -464","240 -438","293 -404","342 -364","385 -318","422 -267","452 -212","475 -154","491 -93","499 -31"}

    {"-968 498","-996 397","-999 226","-995 -319","-993 -452","-892 -498","691 -500","921 -495","988 -460","996 -373","999 49","979 352","970 434","951 459","937 477","924 480","814 492","742 495","633 496","66 498","-299 499"}

    Returns: 781666.7932584676

  19. {"-200 55","-200 -10","-200 -16","-200 -43","-200 -47","-200 -55","-200 -63","-200 -139","-200 -186","-199 -198","-150 -200","-142 -200","-56 -200","-22 -200","-20 -200","27 -200","49 -200","161 -199","190 -198","199 -182","199 -133","199 -109","199 -83","199 0","199 120","199 174","199 182","199 190","198 198","147 199","107 199","70 199","69 199","46 199","32 199","-22 199","-24 199","-74 199","-180 199","-185 198","-198 191","-200 115","-200 87","-200 72"}

    {"500 0","496 62","484 124","464 184","438 240","404 293","364 342","318 385","267 422","212 452","154 475","93 491","31 499","-31 499","-93 491","-154 475","-212 452","-267 422","-318 385","-364 342","-404 293","-438 240","-464 184","-484 124","-496 62","-500 0","-496 -62","-484 -124","-464 -184","-438 -240","-404 -293","-364 -342","-318 -385","-267 -422","-212 -452","-154 -475","-93 -491","-31 -499","31 -499","93 -491","154 -475","212 -452","267 -422","318 -385","364 -342","404 -293","438 -240","464 -184","484 -124","496 -62"}

    Returns: 158771.0

  20. {"870 996","832 998","65 999","-375 999","-477 999","-952 997","-989 975","-999 858","-1000 422","-1000 153","-999 -812","-997 -860","-989 -942","-944 -985","-769 -996","-673 -999","-196 -1000","837 -999","980 -985","988 -919","996 -809","998 -506","997 333","996 834","991 943","988 971","969 980"}

    {"499 31","491 93","475 154","452 212","422 267","385 318","342 364","293 404","240 438","184 464","124 484","62 496","0 500","-62 496","-124 484","-184 464","-240 438","-293 404","-342 364","-385 318","-422 267","-452 212","-475 154","-491 93","-499 31","-499 -31","-491 -93","-475 -154","-452 -212","-422 -267","-385 -318","-342 -364","-293 -404","-240 -438","-184 -464","-124 -484","-62 -496","0 -500","62 -496","124 -484","184 -464","240 -438","293 -404","342 -364","385 -318","422 -267","452 -212","475 -154","491 -93","499 -31"}

    Returns: 781730.0000000002

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: