ZOJ1648 Circuit Board(线段相交)

时间:2023-03-09 18:42:34
ZOJ1648 Circuit Board(线段相交)

裸的判断线段相交

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAABRYAAAAqCAIAAABJOZD4AAARJklEQVR4nO2dvW7jvBKGfUOplEsJjMBt7sBFCgPJHcTVpvgWCHbbtAsEOCkCbFzvdt82AYRt0sSnCU6QJoCRU+hvSM4MR7JsWdIrPEWiH5IaUcN5SYqe/HfzBgAAAAAAAAAAgCiT9eYNAAAAAAAAAAAAUSChwbD5cz1LkiRJLu6Zo+nXaZIkSXL+s/Nygs65P0/CbfFjh3lVif+4QCUE4LD5uUjQXgDQJ9QIcPi0dPstur5heVFeQv+4YGLJ6bc/bWQZxqlZHFk8aboNp9Iz9bgw8o5i9J7CVYOtTAQJDYywEjpJZl9/7yqvvGJnrgCVcMyUbS5tZ39/Ox1cU3jQVAZn459hBX8dkbfILcWT4KDZe5QbxntDkdCF86mpj3YhoSNpjsqL6hK6qPfFPbfm9fIET6/T4EkXAWtRBnpOf4GErmmovBqUirqxlSChgRF/ZDjcQ9sGp84UFcmtq1ndK/+9P68qdpmy22fU92YeNKXqtq66bEjdQMXYM8OK8w4JSOgRAQnd5k2JoUUtg+zCyAIj8KI2CV2Oz3jCprBgfn5wlESc7sM2SGhuT3+xSGh/ALasdm6nTmm0wM5DMlR5L0Lvl3/LbhcdeWPV2hhIaMHUef2ffvtTRrpOeQbS0TNyIhI6nJtTRIHB8LXjCSGhQRxSuwpnQvtlSMVox0fZHebs67XUVA24urLBn9Ne1DO48NRGiCShPS/qvQWn19+CgRx/XO70OiXnp2Wa9G/uEbDpkKIyNQHY0CW0NbINUmDmyc6+/g7nMF7cm/TIgVO4He+V+XHhTuBtIsfMTqxyfayRhZKPwIvWlNC5sWzPLH/kXHNrktClvQ7CUtsRldBVTSqPZtUuOy3fn9tNmPo+aAnt1CX3ll057bXQXm1066oroWVTV63v+U/a4p5ep17lB/1FmMidvbNZVfE7+BY/mEMlFgn9tsZEblD5pdNpUeV+XCTJbHHONbVb+iijw6x8rNdej2Hyjjn4sxhcfmojxDAKnduZeNfsFWD2B7JZlNB6+hb5PYBAdN8oEtoS2bIKwktTUoxefZNS6wHlK8AHmbXkmHfU7MQc17fdKPSwvKhJQgdS1trtwR2llo1I6AFNA4hJaCkocXz6W1nh6tXjPmEdhSaXUJvQSzKjBZfQo9TsmqndDg73YRVvR/cvM9gORkIHlcrb2PGNWhO539aQ0IC0ktcXWcW4P0+S6bd7x32146NqOszNmyd7BjTpSabO+EnE4NpTGyGKhOYcqSBrnUpoldBM+mI6WQVgw3dgRpTQdSJbVsvR0SbypOITufs45sGMultvUA2AazuxXUno/npR83JiToWDhK6LdRS63Ny+Fn/ra3ea3VBeXRL9I1dJdNXNyGavAyw0NST0GKCy1p8Vokpo71voxFUjkNAgTtVK/lwkSXJ+sUiS0+vUdV+t+Ki6DnNDUph9/T0SOdFi8Kc9ta5vswMECc1IX4OEDruWJAktpC+lwy6JNNZH1hxRQteJbB0FEbyYY5DQ600YYyT+oL1RQm+lYLuT0IfqReOj0KUrIWXdk4Qe00Ru5g05/6lbYNASmm76yhAtSWjV1JDQY8D9FtqbGCLO1vYhejive049gYQGHKSVpCuPOO6rHR/VSEITdTGOSa3tBX8DCmNagZfQontsSUJL6YvpuKPQoBmShK4V2XISurpwLBKasZ6hx2EoEvpgvahlInelagpD7EdCD2k5McYI8ptMapX21dmgJbTtqw9qrpYmcrOmhoQeA9L62+JyYt7UMrLFLpEWKhvUuwxqQJsDMszruq92fFSDidzV/vOLxSgqavtTENFHliGMQlPJSj90jIwqS+fQZxRIYiZ9PZ38meIJ1iU2kdsU2Srr1/hHBymhfy6EKRuNJHS/J3IfnBedvGzeQmi9f9m8vVQxYr7HO6F8Zr82by+bP18K+74wR99eNm8vxVP8kpaZFlcVp/0i5mML2TO8WyYVIj9amMs75D+Lzf15fsi38yDwqwF/1L3lX0UHM61+029/uEuqhfHqmLp6z8OrhlZRx0sla4s9gitLgirqqGjq1uhqGflE7l9hXmS9EK7ag+HDtJKbN7kGbuWj6jhMAplKlzdbA4YEf9VOx6o1DC4/tRFSVDC6Xdy/OD2Ji8o9FrL2S1raPHewhZF9xyvt59OXzw+LOtZH1pyg5iuHxMiW1xeFq/Q8Z+BIDXrkwCl6f8oC8/rLJMfcANjuxNhQOWrDEXhRm4Te0OYz28n5QZOEDtfskRMclDgM752E2sHPKpAoXHLxkNCE4Dda/EvYeuV1ZIimhoQGAOwQo4R+actHRR0m06yU7dcIfF2rwZ/81EB7D2t7UdRWOqCAmYeVhONk3ksRFb2K+nhzwuyL+yFIaOEHNckJBjlGt8q3N5TQgZGFko/Ai05eNv8DAAAAAJD5TxHu/Nt1SQD419EGs39+dZwO6IZcXl78p/OSgBECCQ0AAAAAjWIE4PRL2n1hAADgJf2nGLfsuiRglEBCAwAAAEChGKzDMB0AoDu42bzdlwqME0hoAAAAAAAAAADABCQ0AAAAAAAAAABgAhIaAAAAAAAAAAAwAQkNAAAAAAAAAACYmGDDhg0bNmzYsGHDhg0bNmzYTFv6mQIAAAAAAAAAACAKJDQAAAAAAAAAAGACEhoAAAAAAAAAADABCQ0AAAAAAAAAAJiAhAYAAAAAAAAAAExAQgMAAAAAAAAAACYgoQEAAAAAAAAAABOQ0AAAAAAAAAAAgAlIaADAaFktZ0mSJMnlbScFuL1M5o91r7qdJ0kyW666tx4AAOyYu/fJ5HN613UxRn4LAIAAVkKvljMlsFstZ34Ad3uZlBu58HaehNv8NprXY3hdddXq+0m59+T7qnMLGlhPJ58Tn/eb4oSHq49q/9m6uvDunV7i+V961dHVc4NDSl7kUKTw6Weafj4vjvvUPDhGmHxOjl8fui4S6Ia/yxPeL+2DzG1CQoM4bpso1BmmaabNpdJPtPp+wl6YtbBOIn1qebeyag8jjQ7x4gQvQtiGfUcXD1cfk8nH4qnpOU+vR6wp7t4RaXABvyITVAWhygRKB+5rK8di0ESGHn8lF2OjYLkXscBtGsSajqBD4xUyjKZokfSkPAldVVmtkU5olm4J/i5P5CzddlrO63EuRrSP8yQ5Wf6tUqgfgHbPw9VH6Uxvzmh787w4ruTrzRlpOZ5ej6iKvnsnHnw9tR1S8nq4+iCt1HrqCWyh8LTh7ImEXk8DzXxz5nc0gJGQOcr55TzwQoWjSxLXF0n7JZ+bnT+/rVx/dhVNp2rGZMddnT9/hIQeHc5sBb6RDZvmLKQoa+lqORMDJk9Cr76fkHY2ENhqK98jNKsOItLYE8EQ68PVR2tN6t27FIrshKfXo+OPI11C6+c8vR4JUtmJ6EZHVFzkhN15/CFFJugJ7t59NXUsoolW30/803TpK+dibxTi92J+pm15WjmdGjqUwDSaVcxme9bsKLR4G7eXSXJ569TIv8sT0tam2gvAJsvtFN+N1XLm9FIoL5sFfzSSeGppIPfm7HNytr454wcwlQQJVNY+L46d9B+uPqQe3Cxr8aq8JDUPxfNSCq/vPERuzjDmDEoKX5mNRVcNiatvJd1LVDTt/sy2wk2Fl2T+mpHQ9RPp3ICgG7KGONzjNohcc6kM1BQXevo5ZdrZ2/kQB2aJVe2RRnbmck7fWb+/rDLaEN9fP67gWE/FcWnlUJpysrOKviafwVBw84yqc55eVQkdO0eW0PvuDjhEor1RygnuocYSeu/uq6ZjiXfYhf7fRcmlRqNgzrp2D6PZIPwQMZNORIfy6XCNZm2D1JDQt5d5IXQJLdXs8vJ4XuK7EZxsfotCPAFJRaN7aD0lKjpz36wAVhKkeCrOHRlWtCvNK5Csd+9FIsohc17eiLdc+IK+SGjnUYKxUylnt98xn93tyOP5Y2y/569d1V00EnkYnTkxZyK3koibbz5SPZwQHNTFDzv4ptkfcNACr/LCUD+nYZy3RbN7wFCr2iMN13Vk4rmwFTG4l+BqORuKAZ9ej4zStPYh5qgzCY7RsVtJ6FyuqxI6fo4zkdvN0WSrYRMfZpSaNv9QYwm9b/dV17HEFGl8iFXLxd4oxO7FXODmBtElNEknokOFr4+ZRpO9QQ2rhPZ7qb352OQZ8CJefOqShPaHaMz1z4iv+oiejKlQb7A6d+hKggROnSqfLrtlEGZuf1oldDSv4qjg5UVp3RMJLXcNgBGSz+J+9P/O/A/jRtX9wZY5dH9SEP3E1JHQSiLZIdcNQkKPF2fmm9I0F3voAKmQZnbhLaefvUQGN4jKWrWehK4M60Zy1eMII7zBsFcJvZ5S4dqqhK4mn8vy2HIOJRhysIyEDxtVbiniMDxk/jy4Y/dV27GIJipuJCp5Irk0X+XBbXpMz7QFg1jTietQelTWsyczWmEihTFJaK807LyI6pHMmKLLfUumeR1CV+4WEjrwgJXiDZ0j2SNKaCXBT3dnOPe73HP3zqvop9cjZ39DCW3Kq0gkPCTPgoaEBr2Dmx2d+Rlfshbo+1n1CwkN2uXv8oTEPXrTHHw6KAZM+gIzgjIfyjhqYNX2JTT1NgN7cxUJ7S+sRaZeK4ecRFzN6UVZ5b/bZ0RnX0vy2HJOxDiQ0FrAX2MImkvWuNBDuk/31cSxmDSRN68tV3uP8VzkRoFNSrkXe4G3NIglHb/8rA5lnz4job0ZXmp57BKa2cSeEq+uaxMPDNavbNpzCc1IOFbxurkzWreZhDbkRe+LmYMk6c+eSGhM5AYl1VrcjkuTJk6ffF9F9sufSoatlGEid1hUTOQePYEMVptmtrnkx0KrqIKLk5p9sNcbmM6F1iV0+LwG0wGx02+h9zUKzSltP6SxnMMkCwlNkf1GrSHoEFkLdOa+GjqWeNliXQBKLjUahdi91DfmVp7WWBjloVPrmRvN2ASiesuJRQvHfqmvdiDVqi4tLifWwURuZhQ31KWerOV/TrDRcmLRvAjusttC4WVjHize1+Bl+RfQ1SODjgZnEEHbwnJizOiTf4hcJSwnZkkEjIXHeWJpK5VVSXUJLY9XD1lC81atu5yYVUIPzXoZ8RW5W1tOLFizpt3lxNL001fmfOQjnvO8OOZ/9CQ3FJYTE2r+FkPQaWpeKzFajNZo7lhsmkgziJxLnUYhdi81jbmtpzUWpiqScY565Fvo/Upo7uPvSAmYvJyFyz1btPdTE45nzPoXjcuJ8RJaS7DYE+rV58Vx8ENTRSLabw82+VErJa/nxbHXuev2K8fXqOyHhC5+hYs0pdqEdjBUclHKzLUpJoMRQeu4L8N+blWwcp528OsavKj2RXKlovPlfyGhxwS7yhd/Gr+sXaovzcKtuFO9HWGLH53e1gs0q1ojDZuEfpwHL/7APo12fxfa15xbKFtfdlYZHZ29B3PIO5fQ7oLhwSBKT8Kk3SG8SsobIRzSZILL/t3Xdo4l3Llazkhq4oRqSy41GoX4vejPtAWD+MWztYPhTdVt+6osot034u9CF+Ea85zYn1kTzld+dkzMyxtnV34WfLuF6TNJmXv8RaiN5R+1ck6r3KuSYNAfSRB8LkmN+4ZHWRhMOST5d+/nuFxHrxTebTh7okXdX8VAqwZ2R73fGASAg5uGIK37xQSLxaavuMNOOb68TYMWOejf6SkRq9oiDeMotBftDEw/75TnxbHQRt+99+knKvtV2vZRxIUiE8RDukxQzty9+2rsWKyayDJwqLgvY6NguBeTYNzCIJ70VdOJ6lCjhP50F6aJLVfOjkKPkZuzluVf6wkCAPoGJDQAAGwBnSh+9066v/vzXTH/RR4AoN+MWELfvVcS17i+4p4TBAD0G0hoAAAAAICh8X8r1kBkO8R9GQAAAABJRU5ErkJggg==" alt="" width="761" height="23" />

 #include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define eps 1e-12
#define MAXN 2005
#define INF 1000000007
#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a < b ? a : b)
#define mem(a) memset(a,0,sizeof(a)) struct Point{
double x,y;
Point(double x=, double y=):x(x),y(y){}
}; double Cross(Point A, Point B) { return A.x*B.y - A.y*B.x;}//叉积 int N;
struct LINE
{
Point s, e;
} Line[MAXN]; int main()
{
while(~scanf("%d", &N))
{
for(int i=;i<N;i++)
{
scanf("%lf%lf%lf%lf", &Line[i].s.x, &Line[i].s.y, &Line[i].e.x, &Line[i].e.y);
}
int ok = ;
for(int i=;i<N && ok;i++)
{
Point Pi = Point(Line[i].e.x-Line[i].s.x, Line[i].e.y-Line[i].s.y);
for(int j=i+;j<N && ok; j++)
{
double c1 = Cross(Point(Line[j].s.x-Line[i].s.x, Line[j].s.y-Line[i].s.y), Pi);
double c2 = Cross(Point(Line[j].e.x-Line[i].s.x, Line[j].e.y-Line[i].s.y), Pi);
if(c1 * c2 < )
{
Point Pj = Point(Line[j].e.x-Line[j].s.x, Line[j].e.y-Line[j].s.y);
c1 = Cross(Point(Line[i].s.x-Line[j].s.x, Line[i].s.y-Line[j].s.y), Pj);
c2 = Cross(Point(Line[i].e.x-Line[j].s.x, Line[i].e.y-Line[j].s.y), Pj);
if (c1 * c2 < ) ok = ;
}
}
}
printf("%s\n",ok?"ok!":"burned!");
}
return ;
}