#include #include #include #include #include #include #include #define endl "\n" #define point pair #define INF 100000000 using namespace std; ifstream fin("packing.in"); ofstream fout("packing.out"); int f; struct fig { int k; bool placed; vector< point > dots[128]; }; fig figs[512]; vector placed_figs; bool on_line(point a1, point a2, point p) { //check whether p is on the line a or not if(p.first <= max(a1.first, a2.first) && p.first <= min(a1.first, a2.first) && (p.second <= max(a1.second, a2.second) && p.second <= min(a1.second, a2.second)) ) return true; return false; } int dir(point a, point b, point c) { int val = (b.second-a.second)*(c.first-b.first)-(b.first-a.first)*(c.second-b.second); if (val == 0) return 0; //colinear else if(val < 0) return 2; //anti-clockwise direction return 1; //clockwise direction } bool edges_cross(fig fa, fig fb) { for(int i=0; i>f; for(int i=0; i>p; vector< point > dots; double x, y; for(int j=0; j>x>>y; point dot; dot.first=x; dot.second=y; dots.push_back(dot); } fin>>m; figs[i].k=m; for(int j=0; j>k; k--; int dot_idx; for(int u=0; u<=k; ++u) { fin>>dot_idx; point dot=dots[dot_idx]; figs[i].dots[j].push_back(dot); } } } for(int i=0; i