using System;
using System.Collections ;
using System.Collections .Generic ;
using System.Linq ;
public static class Program
{
public static void Main( )
{
var samples = new Dictionary< string, Polygon>
{
{ "a" , new Polygon
{
{ - 5 , 1 } ,
{ - 3 , 3 } ,
{ - 1 , 5 } ,
{ 1 , 5 } ,
{ 3 , 3 } ,
{ 5 , 1 } ,
{ 5 , - 1 } ,
{ 3 , - 3 } ,
{ 1 , - 5 } ,
{ - 1 , - 5 } ,
{ - 3 , - 3 } ,
{ - 5 , - 1 } ,
} } ,
{ "b" , new Polygon
{
{ - 3 , 0 } ,
{ 0 , 3 } ,
{ 3 , 0 } ,
{ 0 , - 3 } ,
} } ,
{ "c" , new Polygon
{
{ 4 , 0 } ,
{ 7 , 3 } ,
{ 10 , 0 } ,
{ 7 , - 3 } ,
} }
} ;
foreach ( var p1 in samples)
foreach ( var p2 in samples) {
var result = IsPolygonsIntersecting( p1.Value , p2.Value ) ;
Console.WriteLine ( "IsPolygonsIntersecting({0}, {1}) = {2}" ,
p1.Key , p2.Key , result) ;
}
}
static bool IsPolygonsIntersecting( Polygon a, Polygon b)
{
foreach ( var polygon in new[ ] { a, b } )
{
for ( int i1 = 0 ; i1 < polygon.Points .Count ; i1++ )
{
int i2 = ( i1 + 1 ) % polygon.Points .Count ;
var p1 = polygon.Points [ i1] ;
var p2 = polygon.Points [ i2] ;
var normal = new Point( p2.Y - p1.Y , p1.X - p2.X ) ;
double ? minA = null , maxA = null ;
foreach ( var p in a.Points )
{
var projected = normal.X * p.X + normal.Y * p.Y ;
if ( minA == null || projected < minA)
minA = projected;
if ( maxA == null || projected > maxA)
maxA = projected;
}
double ? minB = null , maxB = null ;
foreach ( var p in b.Points )
{
var projected = normal.X * p.X + normal.Y * p.Y ;
if ( minB == null || projected < minB)
minB = projected;
if ( maxB == null || projected > maxB)
maxB = projected;
}
if ( maxA < minB || maxB < minA)
return false ;
}
}
return true ;
}
}
class Polygon : IEnumerable< Point> {
public List< Point> Points { get; set; }
public Polygon( ) : this( new Point[ 0 ] ) { }
public Polygon( IEnumerable< Point> points) {
this.Points = points.ToList ( ) ;
}
public IEnumerator< Point> GetEnumerator( ) {
return Points.GetEnumerator ( ) ;
}
IEnumerator IEnumerable.GetEnumerator ( ) {
return this.GetEnumerator ( ) ;
}
public void Add( Point p) {
this.Points .Add ( p) ;
}
public void Add( double x, double y) {
this.Add ( new Point( x, y) ) ;
}
}
class Point {
public double X { get; set; }
public double Y { get; set; }
public Point( double x = 0 , double y = 0 ) {
this.X = x;
this.Y = y;
}
}
dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnM7CnVzaW5nIFN5c3RlbS5Db2xsZWN0aW9ucy5HZW5lcmljOwp1c2luZyBTeXN0ZW0uTGlucTsKCnB1YmxpYyBzdGF0aWMgY2xhc3MgUHJvZ3JhbQp7CiAgICBwdWJsaWMgc3RhdGljIHZvaWQgTWFpbigpCiAgICB7CiAgICAJdmFyIHNhbXBsZXMgPSBuZXcgRGljdGlvbmFyeTxzdHJpbmcsIFBvbHlnb24+CiAgICAJewoJICAgICAgICB7ICJhIiwgbmV3IFBvbHlnb24KCQkgICAgICAgIHsKCQkgICAgICAgICAgICB7IC01LCAgMSB9LAoJCSAgICAgICAgICAgIHsgLTMsICAzIH0sCgkJICAgICAgICAgICAgeyAtMSwgIDUgfSwKCQkgICAgICAgICAgICB7ICAxLCAgNSB9LAoJCSAgICAgICAgICAgIHsgIDMsICAzIH0sCgkJICAgICAgICAgICAgeyAgNSwgIDEgfSwKCQkgICAgICAgICAgICB7ICA1LCAtMSB9LAoJCSAgICAgICAgICAgIHsgIDMsIC0zIH0sCgkJICAgICAgICAgICAgeyAgMSwgLTUgfSwKCQkgICAgICAgICAgICB7IC0xLCAtNSB9LAoJCSAgICAgICAgICAgIHsgLTMsIC0zIH0sCgkJICAgICAgICAgICAgeyAtNSwgLTEgfSwKCQkgICAgICAgIH0gfSwKCSAgICAgICAgeyAiYiIsIG5ldyBQb2x5Z29uCgkJICAgICAgICB7CgkJICAgICAgICAgICAgeyAtMywgIDAgfSwKCQkgICAgICAgICAgICB7ICAwLCAgMyB9LAoJCSAgICAgICAgICAgIHsgIDMsICAwIH0sCgkJICAgICAgICAgICAgeyAgMCwgLTMgfSwKCQkgICAgICAgIH0gfSwKCSAgICAgICAgeyAiYyIsIG5ldyBQb2x5Z29uCgkJICAgICAgICB7CgkJICAgICAgICAgICAgeyAgNCwgIDAgfSwKCQkgICAgICAgICAgICB7ICA3LCAgMyB9LAoJCSAgICAgICAgICAgIHsgMTAsICAwIH0sCgkJICAgICAgICAgICAgeyAgNywgLTMgfSwKCQkgICAgICAgIH0gfQogICAgICAgIH07CiAgICAgICAgCiAgICAgICAgZm9yZWFjaCAodmFyIHAxIGluIHNhbXBsZXMpCiAgICAgICAgZm9yZWFjaCAodmFyIHAyIGluIHNhbXBsZXMpIHsKICAgICAgICAJdmFyIHJlc3VsdCA9IElzUG9seWdvbnNJbnRlcnNlY3RpbmcocDEuVmFsdWUsIHAyLlZhbHVlKTsKICAgICAgICAJQ29uc29sZS5Xcml0ZUxpbmUoIklzUG9seWdvbnNJbnRlcnNlY3RpbmcoezB9LCB7MX0pID0gezJ9IiwKICAgICAgICAJCXAxLktleSwgcDIuS2V5LCByZXN1bHQpOwogICAgICAgIH0KICAgIH0KICAgIAogICAgc3RhdGljIGJvb2wgSXNQb2x5Z29uc0ludGVyc2VjdGluZyhQb2x5Z29uIGEsIFBvbHlnb24gYikKICAgIHsKICAgICAgICBmb3JlYWNoICh2YXIgcG9seWdvbiBpbiBuZXdbXSB7IGEsIGIgfSkKICAgICAgICB7CiAgICAgICAgICAgIGZvciAoaW50IGkxID0gMDsgaTEgPCBwb2x5Z29uLlBvaW50cy5Db3VudDsgaTErKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaW50IGkyID0gKGkxICsgMSkgJSBwb2x5Z29uLlBvaW50cy5Db3VudDsKICAgICAgICAgICAgICAgIHZhciBwMSA9IHBvbHlnb24uUG9pbnRzW2kxXTsKICAgICAgICAgICAgICAgIHZhciBwMiA9IHBvbHlnb24uUG9pbnRzW2kyXTsKICAgIAogICAgICAgICAgICAgICAgdmFyIG5vcm1hbCA9IG5ldyBQb2ludChwMi5ZIC0gcDEuWSwgcDEuWCAtIHAyLlgpOwogICAgCiAgICAgICAgICAgICAgICBkb3VibGU/IG1pbkEgPSBudWxsLCBtYXhBID0gbnVsbDsKICAgICAgICAgICAgICAgIGZvcmVhY2ggKHZhciBwIGluIGEuUG9pbnRzKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHZhciBwcm9qZWN0ZWQgPSBub3JtYWwuWCAqIHAuWCArIG5vcm1hbC5ZICogcC5ZOwogICAgICAgICAgICAgICAgICAgIGlmIChtaW5BID09IG51bGwgfHwgcHJvamVjdGVkIDwgbWluQSkKICAgICAgICAgICAgICAgICAgICAgICAgbWluQSA9IHByb2plY3RlZDsKICAgICAgICAgICAgICAgICAgICBpZiAobWF4QSA9PSBudWxsIHx8IHByb2plY3RlZCA+IG1heEEpCiAgICAgICAgICAgICAgICAgICAgICAgIG1heEEgPSBwcm9qZWN0ZWQ7CiAgICAgICAgICAgICAgICB9CiAgICAKICAgICAgICAgICAgICAgIGRvdWJsZT8gbWluQiA9IG51bGwsIG1heEIgPSBudWxsOwogICAgICAgICAgICAgICAgZm9yZWFjaCAodmFyIHAgaW4gYi5Qb2ludHMpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgdmFyIHByb2plY3RlZCA9IG5vcm1hbC5YICogcC5YICsgbm9ybWFsLlkgKiBwLlk7CiAgICAgICAgICAgICAgICAgICAgaWYgKG1pbkIgPT0gbnVsbCB8fCBwcm9qZWN0ZWQgPCBtaW5CKQogICAgICAgICAgICAgICAgICAgICAgICBtaW5CID0gcHJvamVjdGVkOwogICAgICAgICAgICAgICAgICAgIGlmIChtYXhCID09IG51bGwgfHwgcHJvamVjdGVkID4gbWF4QikKICAgICAgICAgICAgICAgICAgICAgICAgbWF4QiA9IHByb2plY3RlZDsKICAgICAgICAgICAgICAgIH0KICAgIAogICAgICAgICAgICAgICAgaWYgKG1heEEgPCBtaW5CIHx8IG1heEIgPCBtaW5BKQogICAgICAgICAgICAgICAgICAgIHJldHVybiBmYWxzZTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICByZXR1cm4gdHJ1ZTsKICAgIH0KfQogICAgCmNsYXNzIFBvbHlnb24gOiBJRW51bWVyYWJsZTxQb2ludD4gewogICAgcHVibGljIExpc3Q8UG9pbnQ+IFBvaW50cyB7IGdldDsgc2V0OyB9CiAgICAKICAgIHB1YmxpYyBQb2x5Z29uKCkgOiB0aGlzKG5ldyBQb2ludFswXSkgeyAgfQogICAgcHVibGljIFBvbHlnb24oSUVudW1lcmFibGU8UG9pbnQ+IHBvaW50cykgewogICAgICAgIHRoaXMuUG9pbnRzID0gcG9pbnRzLlRvTGlzdCgpOwogICAgfQogICAgCiAgICBwdWJsaWMgSUVudW1lcmF0b3I8UG9pbnQ+IEdldEVudW1lcmF0b3IoKSB7CiAgICAgICAgcmV0dXJuIFBvaW50cy5HZXRFbnVtZXJhdG9yKCk7CiAgICB9CiAgICAKICAgIElFbnVtZXJhdG9yIElFbnVtZXJhYmxlLkdldEVudW1lcmF0b3IoKSB7CiAgICAgICAgcmV0dXJuIHRoaXMuR2V0RW51bWVyYXRvcigpOwogICAgfQogICAgCiAgICBwdWJsaWMgdm9pZCBBZGQoUG9pbnQgcCkgewogICAgICAgIHRoaXMuUG9pbnRzLkFkZChwKTsKICAgIH0KICAgIAogICAgcHVibGljIHZvaWQgQWRkKGRvdWJsZSB4LCBkb3VibGUgeSkgewogICAgICAgIHRoaXMuQWRkKG5ldyBQb2ludCh4LCB5KSk7CiAgICB9Cn0KCmNsYXNzIFBvaW50IHsKICAgIHB1YmxpYyBkb3VibGUgWCB7IGdldDsgc2V0OyB9CiAgICBwdWJsaWMgZG91YmxlIFkgeyBnZXQ7IHNldDsgfQogICAgCiAgICBwdWJsaWMgUG9pbnQoZG91YmxlIHggPSAwLCBkb3VibGUgeSA9IDApIHsKICAgICAgICB0aGlzLlggPSB4OwogICAgICAgIHRoaXMuWSA9IHk7CiAgICB9Cn0=