poj 1092 Farmland (Geometry)

　　怎么最近做几何题都这么蛋疼，提交C++过不了交G++就过了。据我估计，原因是用了atan2这个函数，或者是其他一些函数造成了精度的影响。不管怎样，这题最后还是过了~

　　解释一下题意，题目的意思是，给出一些边和点，要求找到简单多边形，也就是没有重复的点的多边形，而且多边形里面不能有其他的点。

　　于是，还是之前的做法，对于每一条边作为起始边，从这条边出发，找最往左的一个点，然后移动到那里。不停这样的模拟，直到走回起始位置，就计算多边形是由多少条边构成的。如果满足就对计数器加一，最后输出结果即可。

最早通过的版本的写法是可以不用检查有没有点在多边形里面的：

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <cmath>

 #include <vector>

 #include <map>

 using namespace std;

 const int N = ;

 struct Point {

     int x, y;

     Point() {}

     Point(int x, int y) : x(x), y(y) {}

     Point operator + (Point a) { return Point(x + a.x, y + a.y);}

     Point operator - (Point a) { return Point(x - a.x, y - a.y);}

 } pt[N];

 typedef pair<int, int> PII;

 typedef vector<Point> VPT;

 typedef vector<int> VI;

 inline double angle(Point x) { return atan2((double) x.y, (double) x.x);}

 inline int cross(Point x, Point y) { return x.x * y.y - x.y * y.x;}

 VI rel[N];

 Point ori;

 map<int, int> pid;

 map<int, int> nx[N];

 bool vis[N][N], vs[N];

 int rec[N];

 inline bool cmp(int a, int b) { return angle(pt[a] - ori) < angle(pt[b] - ori);}

 double area() {

     double ret = 0.0;

     rec[rec[] + ] = rec[];

     for (int i = ; i <= rec[]; i++) ret += cross(pt[rec[i]], pt[rec[i + ]]);

     return ret / 2.0;

 }

 int main() {

 //    freopen("in", "r", stdin);

 //    freopen("out", "w", stdout);

     int T, n, k, x, id;

     scanf("%d", &T);

     while (T-- && ~scanf("%d", &n)) {

         pid.clear();

         for (int i = ; i < n; i++) {

             scanf("%d", &id);

             if (pid.find(id) == pid.end()) pid[id] = pid.size();

             rel[pid[id]].clear();

             nx[pid[id]].clear();

             scanf("%d%d", &pt[pid[id]].x, &pt[pid[id]].y);

             scanf("%d", &k);

             while (k--) {

                 scanf("%d", &x);

                 if (pid.find(x) == pid.end()) pid[x] = pid.size();

                 rel[pid[id]].push_back(pid[x]);

             }

         }

 //        for (int i = 1; i <= n; i++) cout << i << ' ' << pid[i] << endl;

         scanf("%d", &k);

         for (int i = , sz; i <= n; i++) {

             ori = pt[i];

             sort(rel[i].begin(), rel[i].end(), cmp);

             sz = rel[i].size();

             if (sz <= ) continue;

             rel[i].push_back(rel[i][]);

             for (int j = ; j < sz; j++) nx[rel[i][j + ]][i] = rel[i][j];

             rel[i].pop_back();

         }

         memset(vis, , sizeof(vis));

         int cnt = ;

         for (int i = , len, t; i <= n; i++) {

             for (int j = , sz = rel[i].size(); j < sz; j++) {

                 memset(vs, , sizeof(vs));

                 rec[] = ;

                 int ls = i, cr = rel[i][j];

                 rec[++rec[]] = ls;

                 bool ok = true;

                 vs[cr] = true;

                 if (vis[ls][cr]) continue;

                 len = ;

 //                cout << "start " << i << ' ';

                 while (cr != i) {

                     rec[++rec[]] = cr;

 //                    cout << cr << ' ';

                     t = cr;

                     cr = nx[ls][cr];

                     if (cr <= ) {

                         len = -;

                         break;

                     }

                     if (vs[cr]) ok = false;

                     vs[cr] = true;

                     ls = t;

                     vis[ls][cr] = true;

                     len++;

                 }

 //                cout << "~~" << len << endl;

                 if (ok && len == k && vs[nx[ls][cr]] && area() > 0.0) cnt++;

             }

         }

         printf("%d\n", cnt);

     }

     return ;

 }

　　因为开始的时候wa太多次了，所以我的代码对标号重标号了。

然后不停的改啊改，最后改到把检查点在多边形内的操作也加上去了~

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <cmath>

 #include <vector>

 #include <map>

 using namespace std;

 const int N = ;

 struct Point {

     int x, y;

     Point() {}

     Point(int x, int y) : x(x), y(y) {}

     Point operator + (Point a) { return Point(x + a.x, y + a.y);}

     Point operator - (Point a) { return Point(x - a.x, y - a.y);}

 } pt[N];

 typedef pair<int, int> PII;

 typedef vector<Point> VPT;

 typedef vector<int> VI;

 inline double angle(Point x) { return atan2((double) x.y, (double) x.x);}

 inline int cross(Point x, Point y) { return x.x * y.y - x.y * y.x;}

 VI rel[N];

 Point ori;

 map<int, int> pid;

 map<int, int> nx[N];

 bool vis[N][N], vs[N];

 int rec[N];

 inline bool cmp(int a, int b) { return angle(pt[a] - ori) < angle(pt[b] - ori);}

 double area() {

     double ret = 0.0;

     rec[rec[] + ] = rec[];

     for (int i = ; i <= rec[]; i++) ret += cross(pt[rec[i]], pt[rec[i + ]]);

     return ret / 2.0;

 }

 bool test(int p) {

     int sz = rec[], wn = ;

     rec[sz + ] = rec[];

     for (int i = ; i <= sz; i++) {

         if (pt[p].x == pt[rec[i]].x && pt[p].y == pt[rec[i]].y) return false;

         int k = cross(pt[rec[i + ]] - pt[rec[i]], pt[p] - pt[rec[i]]);

         int d1 = pt[rec[i]].y - pt[p].y;

         int d2 = pt[rec[i + ]].y - pt[p].y;

         if (k >  && d1 <=  && d2 > ) wn++;

         if (k <  && d2 <=  && d1 > ) wn--;

     }

     return wn != ;

 }

 bool check() {

 //    for (int i = 1; i <= rec[0]; i++) cout << rec[i] << ' '; cout << endl;

     for (int i = , sz = pid.size(); i <= sz; i++) {

         if (test(i)) return false;

     }

     return true;

 }

 int main() {

 //    freopen("in", "r", stdin);

 //    freopen("out", "w", stdout);

     int T, n, k, x, id;

     scanf("%d", &T);

     while (T-- && ~scanf("%d", &n)) {

         pid.clear();

         for (int i = ; i < n; i++) {

             scanf("%d", &id);

             if (pid.find(id) == pid.end()) pid[id] = pid.size();

             rel[pid[id]].clear();

             nx[pid[id]].clear();

             scanf("%d%d", &pt[pid[id]].x, &pt[pid[id]].y);

             scanf("%d", &k);

             while (k--) {

                 scanf("%d", &x);

                 if (pid.find(x) == pid.end()) pid[x] = pid.size();

                 rel[pid[id]].push_back(pid[x]);

             }

         }

 //        for (int i = 1; i <= n; i++) cout << i << ' ' << pid[i] << endl;

         scanf("%d", &k);

         if (k < ) { puts(""); continue;}

         for (int i = , sz; i <= n; i++) {

             ori = pt[i];

             sort(rel[i].begin(), rel[i].end(), cmp);

             sz = rel[i].size();

             if (sz <= ) continue;

             rel[i].push_back(rel[i][]);

             for (int j = ; j < sz; j++) nx[rel[i][j + ]][i] = rel[i][j];

             rel[i].pop_back();

         }

         memset(vis, , sizeof(vis));

         int cnt = ;

         for (int i = , len, t; i <= n; i++) {

             for (int j = , sz = rel[i].size(); j < sz; j++) {

                 rec[] = ;

                 int ls = i, cr = rel[i][j];

                 if (vis[ls][cr]) continue;

                 vis[ls][cr] = true;

                 bool ok = true;

                 memset(vs, , sizeof(vs));

                 len = ;

 //                cout << "start " << i << ' ';

                 while (nx[ls][cr]) {

                     rec[++rec[]] = cr;

 //                    cout << cr << ' ';

                     t = cr;

                     cr = nx[ls][cr];

                     if (cr <= ) {

                         len = -;

                         break;

                     }

                     if (vs[cr]) ok = false;

                     vs[cr] = true;

                     ls = t;

                     if (vis[ls][cr]) break;

                     vis[ls][cr] = true;

                     len++;

                 }

 //                cout << "~~" << len << endl;

                 if (ok && len == k && ls == i && area() >= 1e- && check()) cnt++;

             }

         }

         printf("%d\n", cnt);

     }

     return ;

 }

——written by Lyon

巴特西

poj 1092 Farmland (Geometry)

最新文章

热门文章