poj 3335 /poj 3130/ poj 1474 半平面交判断核是否存在 / poj1279 半平面交求核的面积...

Bertha 。 2021-11-17 15:22 310阅读 0赞

1 /***************
      2 poj 3335  点序顺时针
      3 ***************/
      4 #include <iostream>
      5 #include <cmath>
      6 #include <algorithm>
      7 using namespace std;
      8 const double eps = 1e-8;
      9 const double maxn = 0x7f7f7f7f;
     10 int dcmp(double x){
     11     if(fabs(x)<eps)
     12         return 0;
     13     else
     14         return x<0?-1:1;
     15 }
     16 struct point {
     17     double x,y;
     18     point (double x=0,double y =0):x(x),y(y){}
     19 };
     20 point p[150];
     21 typedef point Vector;
     22 
     23 struct polygon{
     24     point p[150];
     25     int Size;
     26 };
     27 
     28 struct line{
     29     point fir,sec;
     30     line(point a = point(),point b = point()){
     31         fir = a;
     32         sec = b;
     33     }
     34 };
     35 
     36 Vector operator -(point a,point b){
     37     return Vector(a.x-b.x,a.y-b.y);
     38 }
     39 
     40 Vector operator *(Vector a,double p){
     41     return Vector (a.x*p,a.y*p);
     42 }
     43 Vector operator + (Vector a,Vector b){
     44     return Vector (a.x+b.x,a.y+b.y);
     45 }
     46 
     47 double cross(Vector a,Vector b){
     48     return a.x*b.y-a.y*b.x;
     49 }
     50 
     51 double dot(Vector a,Vector b){
     52     return a.x*b.x+a.y*b.y;
     53 }
     54 
     55 point getLineIntersection(point p,Vector v,point q,Vector w){
     56     Vector u = p-q;
     57     double t = cross(w,u)/cross(v,w);
     58     return p+v*t;
     59 }
     60 
     61 bool onsegment(point p,point a1,point a2){
     62     return dcmp(cross(a1-p,a2-p))==0&&dcmp(dot(a1-p,a2-p))<0;
     63 }
     64 
     65 polygon cutploygon(polygon poly,line ln){
     66     polygon newploy;
     67     int m=0;
     68     int n = poly.Size;
     69     point a = ln.fir,b = ln.sec;
     70     for(int i=0;i<n;i++){
     71         point c = poly.p[i];
     72         point d = poly.p[(i+1)%n];
     73         double cc = cross(b-a,c-a);
     74         double dd = cross(b-a,d-a);
     75         if(cc>=0)
     76             newploy.p[m++] = c;
     77         if(cc*dd<0)
     78             newploy.p[m++] = getLineIntersection(a,b-a,c,d-c);
     79     }
     80     newploy.Size = m;
     81     return newploy;
     82 }
     83 
     84 int main()
     85 {
     86     int t;
     87     cin>>t;
     88     int n;
     89     while(t--){
     90         cin>>n;
     91         for(int i=0;i<n;i++)
     92             cin>>p[i].x>>p[i].y;
     93         polygon poly;
     94         poly.Size = 4;
     95         poly.p[0].x = -maxn;
     96         poly.p[0].y = -maxn;
     97         poly.p[1].x = maxn;
     98         poly.p[1].y = -maxn;
     99         poly.p[2].x = maxn;
    100         poly.p[2].y = maxn;
    101         poly.p[3].x = -maxn;
    102         poly.p[3].y = maxn;
    103         bool flag = true;
    104         for(int i=1;i<=n;i++){
    105             line ln;
    106             ln.fir = p[i%n];
    107             ln.sec = p[i-1];
    108             poly = cutploygon(poly,ln);
    109             if(poly.Size==0){
    110                 flag = false;
    111                 break;
    112             }
    113         }
    114         if(!flag)
    115             cout<<"NO"<<endl;
    116         else
    117             cout<<"YES"<<endl;
    118     }
    119     return 0;
    120 }
    121 
    122 /****************************************/
    123 poj 3130  点序逆时针
    124 /****************************************/
    125 
    126 #include <iostream>
    127 #include <cmath>
    128 #include <algorithm>
    129 using namespace std;
    130 const double eps = 1e-8;
    131 const double maxn = 0x7f7f7f7f;
    132 int dcmp(double x){
    133     if(fabs(x)<eps)
    134         return 0;
    135     else
    136         return x<0?-1:1;
    137 }
    138 struct point {
    139     double x,y;
    140     point (double x=0,double y =0):x(x),y(y){}
    141 };
    142 point p[150];
    143 typedef point Vector;
    144 
    145 struct polygon{
    146     point p[150];
    147     int Size;
    148 };
    149 
    150 struct line{
    151     point fir,sec;
    152     line(point a = point(),point b = point()){
    153         fir = a;
    154         sec = b;
    155     }
    156 };
    157 
    158 Vector operator -(point a,point b){
    159     return Vector(a.x-b.x,a.y-b.y);
    160 }
    161 
    162 Vector operator *(Vector a,double p){
    163     return Vector (a.x*p,a.y*p);
    164 }
    165 Vector operator + (Vector a,Vector b){
    166     return Vector (a.x+b.x,a.y+b.y);
    167 }
    168 
    169 double cross(Vector a,Vector b){
    170     return a.x*b.y-a.y*b.x;
    171 }
    172 
    173 double dot(Vector a,Vector b){
    174     return a.x*b.x+a.y*b.y;
    175 }
    176 
    177 point getLineIntersection(point p,Vector v,point q,Vector w){
    178     Vector u = p-q;
    179     double t = cross(w,u)/cross(v,w);
    180     return p+v*t;
    181 }
    182 
    183 bool onsegment(point p,point a1,point a2){
    184     return dcmp(cross(a1-p,a2-p))==0&&dcmp(dot(a1-p,a2-p))<0;
    185 }
    186 
    187 polygon cutploygon(polygon poly,line ln){
    188     polygon newploy;
    189     int m=0;
    190     int n = poly.Size;
    191     point a = ln.fir,b = ln.sec;
    192     for(int i=0;i<n;i++){
    193         point c = poly.p[i];
    194         point d = poly.p[(i+1)%n];
    195         double cc = cross(b-a,c-a);
    196         double dd = cross(b-a,d-a);
    197         if(cc>=0)
    198             newploy.p[m++] = c;
    199         if(cc*dd<0)
    200             newploy.p[m++] = getLineIntersection(a,b-a,c,d-c);
    201     }
    202     newploy.Size = m;
    203     return newploy;
    204 }
    205 
    206 int main()
    207 {
    208     int n;
    209     while(cin>>n&&n){
    210         for(int i=0;i<n;i++)
    211             cin>>p[i].x>>p[i].y;
    212         polygon poly;
    213         poly.Size = 4;
    214         poly.p[0].x = -maxn;
    215         poly.p[0].y = -maxn;
    216         poly.p[1].x = maxn;
    217         poly.p[1].y = -maxn;
    218         poly.p[2].x = maxn;
    219         poly.p[2].y = maxn;
    220         poly.p[3].x = -maxn;
    221         poly.p[3].y = maxn;
    222         bool flag = true;
    223         for(int i=0;i<n;i++){
    224             line ln;
    225             ln.fir = p[i%n];
    226             ln.sec = p[(i+1)%n];
    227             poly = cutploygon(poly,ln);
    228             if(poly.Size==0){
    229                 flag = false;
    230                 break;
    231             }
    232         }
    233         if(!flag)
    234             cout<<"0"<<endl;
    235         else
    236             cout<<"1"<<endl;
    237     }
    238     return 0;
    239 }
    240 
    241 
    242 /*************************************/
    243 poj  1474  点序顺时针
    244 /*************************************/
    245 #include <iostream>
    246 #include <cmath>
    247 #include <algorithm>
    248 using namespace std;
    249 const double eps = 1e-8;
    250 const double maxn = 0x7f7f7f7f;
    251 int dcmp(double x){
    252     if(fabs(x)<eps)
    253         return 0;
    254     else
    255         return x<0?-1:1;
    256 }
    257 struct point {
    258     double x,y;
    259     point (double x=0,double y =0):x(x),y(y){}
    260 };
    261 point p[150];
    262 typedef point Vector;
    263 
    264 struct polygon{
    265     point p[150];
    266     int Size;
    267 };
    268 
    269 struct line{
    270     point fir,sec;
    271     line(point a = point(),point b = point()){
    272         fir = a;
    273         sec = b;
    274     }
    275 };
    276 
    277 Vector operator -(point a,point b){
    278     return Vector(a.x-b.x,a.y-b.y);
    279 }
    280 
    281 Vector operator *(Vector a,double p){
    282     return Vector (a.x*p,a.y*p);
    283 }
    284 Vector operator + (Vector a,Vector b){
    285     return Vector (a.x+b.x,a.y+b.y);
    286 }
    287 
    288 double cross(Vector a,Vector b){
    289     return a.x*b.y-a.y*b.x;
    290 }
    291 
    292 double dot(Vector a,Vector b){
    293     return a.x*b.x+a.y*b.y;
    294 }
    295 
    296 point getLineIntersection(point p,Vector v,point q,Vector w){
    297     Vector u = p-q;
    298     double t = cross(w,u)/cross(v,w);
    299     return p+v*t;
    300 }
    301 
    302 bool onsegment(point p,point a1,point a2){
    303     return dcmp(cross(a1-p,a2-p))==0&&dcmp(dot(a1-p,a2-p))<0;
    304 }
    305 
    306 polygon cutploygon(polygon poly,line ln){
    307     polygon newploy;
    308     int m=0;
    309     int n = poly.Size;
    310     point a = ln.fir,b = ln.sec;
    311     for(int i=0;i<n;i++){
    312         point c = poly.p[i];
    313         point d = poly.p[(i+1)%n];
    314         double cc = cross(b-a,c-a);
    315         double dd = cross(b-a,d-a);
    316         if(cc>=0)
    317             newploy.p[m++] = c;
    318         if(cc*dd<0)
    319             newploy.p[m++] = getLineIntersection(a,b-a,c,d-c);
    320     }
    321     newploy.Size = m;
    322     return newploy;
    323 }
    324 
    325 int main()
    326 {
    327     int n;
    328     int cnt =1;
    329     while(cin>>n&&n){
    330         for(int i=0;i<n;i++)
    331             cin>>p[i].x>>p[i].y;
    332         polygon poly;
    333         poly.Size = 4;
    334         poly.p[0].x = -maxn;
    335         poly.p[0].y = -maxn;
    336         poly.p[1].x = maxn;
    337         poly.p[1].y = -maxn;
    338         poly.p[2].x = maxn;
    339         poly.p[2].y = maxn;
    340         poly.p[3].x = -maxn;
    341         poly.p[3].y = maxn;
    342         bool flag = true;
    343         for(int i=1;i<=n;i++){
    344             line ln;
    345             ln.fir = p[i%n];
    346             ln.sec = p[i-1];
    347             poly = cutploygon(poly,ln);
    348             if(poly.Size==0){
    349                 flag = false;
    350                 break;
    351             }
    352         }
    353         //cout<<poly.Size<<endl;
    354         cout<<"Floor #"<<cnt++<<endl;
    355         if(!flag)
    356             cout<<"Surveillance is impossible."<<endl;
    357         else
    358             cout<<"Surveillance is possible."<<endl;
    359         cout<<endl;
    360     }
    361     return 0;
    362 }
    363 
    364 
    365 /**********************************
    366 poj 1279  点序顺时针
    367 **********************************/
    368 #include <iostream>
    369 #include <cmath>
    370 #include <algorithm>
    371 #include <cstdio>
    372 using namespace std;
    373 const double eps = 1e-8;
    374 const double maxn = 0x7f7f7f7f;
    375 int dcmp(double x){
    376     if(fabs(x)<eps)
    377         return 0;
    378     else
    379         return x<0?-1:1;
    380 }
    381 struct point {
    382     double x,y;
    383     point (double x=0,double y =0):x(x),y(y){}
    384 };
    385 point p[2000];
    386 typedef point Vector;
    387 
    388 struct polygon{
    389     point p[2000];
    390     int Size;
    391 };
    392 
    393 struct line{
    394     point fir,sec;
    395     line(point a = point(),point b = point()){
    396         fir = a;
    397         sec = b;
    398     }
    399 };
    400 
    401 Vector operator -(point a,point b){
    402     return Vector(a.x-b.x,a.y-b.y);
    403 }
    404 
    405 Vector operator *(Vector a,double p){
    406     return Vector (a.x*p,a.y*p);
    407 }
    408 Vector operator + (Vector a,Vector b){
    409     return Vector (a.x+b.x,a.y+b.y);
    410 }
    411 
    412 double cross(Vector a,Vector b){
    413     return a.x*b.y-a.y*b.x;
    414 }
    415 
    416 double dot(Vector a,Vector b){
    417     return a.x*b.x+a.y*b.y;
    418 }
    419 
    420 point getLineIntersection(point p,Vector v,point q,Vector w){
    421     Vector u = p-q;
    422     double t = cross(w,u)/cross(v,w);
    423     return p+v*t;
    424 }
    425 
    426 bool onsegment(point p,point a1,point a2){
    427     return dcmp(cross(a1-p,a2-p))==0&&dcmp(dot(a1-p,a2-p))<0;
    428 }
    429 
    430 polygon cutploygon(polygon poly,line ln){
    431     polygon newploy;
    432     int m=0;
    433     int n = poly.Size;
    434     point a = ln.fir,b = ln.sec;
    435     for(int i=0;i<n;i++){
    436         point c = poly.p[i];
    437         point d = poly.p[(i+1)%n];
    438         double cc = cross(b-a,c-a);
    439         double dd = cross(b-a,d-a);
    440         if(cc>=0)
    441             newploy.p[m++] = c;
    442         if(cc*dd<0)
    443             newploy.p[m++] = getLineIntersection(a,b-a,c,d-c);
    444     }
    445     newploy.Size = m;
    446     return newploy;
    447 }
    448 
    449 double polyArea(point *p,int n){
    450     double area =0;
    451     for(int i=1;i<n-1;i++){
    452         area += cross(p[i]-p[0],p[i+1]-p[0]);
    453     }
    454     return area/2;
    455 }
    456 
    457 int main()
    458 {
    459     int t;
    460     cin>>t;
    461     int n;
    462     while(t--){
    463         cin>>n;
    464         for(int i=0;i<n;i++)
    465             cin>>p[i].x>>p[i].y;
    466         polygon poly;
    467         poly.Size = 4;
    468         poly.p[0].x = -maxn;
    469         poly.p[0].y = -maxn;
    470         poly.p[1].x = maxn;
    471         poly.p[1].y = -maxn;
    472         poly.p[2].x = maxn;
    473         poly.p[2].y = maxn;
    474         poly.p[3].x = -maxn;
    475         poly.p[3].y = maxn;
    476         bool flag = true;
    477         for(int i=1;i<=n;i++){
    478             line ln;
    479             ln.fir = p[i%n];
    480             ln.sec = p[i-1];
    481             poly = cutploygon(poly,ln);
    482             if(poly.Size==0){
    483                 flag = false;
    484                 break;
    485             }
    486         }
    487         double res;
    488         if(!flag)
    489             res =0;
    490         else{
    491             res = polyArea(poly.p,poly.Size);
    492         }
    493         printf("%.2lf\n",res);
    494     }
    495     return 0;
    496 }

转载于:https://www.cnblogs.com/Bang-cansee/p/3724063.html