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

 /***************
poj 3335 点序顺时针
***************/
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps = 1e-;
const double maxn = 0x7f7f7f7f;
int dcmp(double x){
if(fabs(x)<eps)
return ;
else
return x<?-:;
}
struct point {
double x,y;
point (double x=,double y =):x(x),y(y){}
};
point p[];
typedef point Vector; struct polygon{
point p[];
int Size;
}; struct line{
point fir,sec;
line(point a = point(),point b = point()){
fir = a;
sec = b;
}
}; Vector operator -(point a,point b){
return Vector(a.x-b.x,a.y-b.y);
} Vector operator *(Vector a,double p){
return Vector (a.x*p,a.y*p);
}
Vector operator + (Vector a,Vector b){
return Vector (a.x+b.x,a.y+b.y);
} double cross(Vector a,Vector b){
return a.x*b.y-a.y*b.x;
} double dot(Vector a,Vector b){
return a.x*b.x+a.y*b.y;
} point getLineIntersection(point p,Vector v,point q,Vector w){
Vector u = p-q;
double t = cross(w,u)/cross(v,w);
return p+v*t;
} bool onsegment(point p,point a1,point a2){
return dcmp(cross(a1-p,a2-p))==&&dcmp(dot(a1-p,a2-p))<;
} polygon cutploygon(polygon poly,line ln){
polygon newploy;
int m=;
int n = poly.Size;
point a = ln.fir,b = ln.sec;
for(int i=;i<n;i++){
point c = poly.p[i];
point d = poly.p[(i+)%n];
double cc = cross(b-a,c-a);
double dd = cross(b-a,d-a);
if(cc>=)
newploy.p[m++] = c;
if(cc*dd<)
newploy.p[m++] = getLineIntersection(a,b-a,c,d-c);
}
newploy.Size = m;
return newploy;
} int main()
{
int t;
cin>>t;
int n;
while(t--){
cin>>n;
for(int i=;i<n;i++)
cin>>p[i].x>>p[i].y;
polygon poly;
poly.Size = ;
poly.p[].x = -maxn;
poly.p[].y = -maxn;
poly.p[].x = maxn;
poly.p[].y = -maxn;
poly.p[].x = maxn;
poly.p[].y = maxn;
poly.p[].x = -maxn;
poly.p[].y = maxn;
bool flag = true;
for(int i=;i<=n;i++){
line ln;
ln.fir = p[i%n];
ln.sec = p[i-];
poly = cutploygon(poly,ln);
if(poly.Size==){
flag = false;
break;
}
}
if(!flag)
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;
}
return ;
} /****************************************/
poj 点序逆时针
/****************************************/ #include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps = 1e-;
const double maxn = 0x7f7f7f7f;
int dcmp(double x){
if(fabs(x)<eps)
return ;
else
return x<?-:;
}
struct point {
double x,y;
point (double x=,double y =):x(x),y(y){}
};
point p[];
typedef point Vector; struct polygon{
point p[];
int Size;
}; struct line{
point fir,sec;
line(point a = point(),point b = point()){
fir = a;
sec = b;
}
}; Vector operator -(point a,point b){
return Vector(a.x-b.x,a.y-b.y);
} Vector operator *(Vector a,double p){
return Vector (a.x*p,a.y*p);
}
Vector operator + (Vector a,Vector b){
return Vector (a.x+b.x,a.y+b.y);
} double cross(Vector a,Vector b){
return a.x*b.y-a.y*b.x;
} double dot(Vector a,Vector b){
return a.x*b.x+a.y*b.y;
} point getLineIntersection(point p,Vector v,point q,Vector w){
Vector u = p-q;
double t = cross(w,u)/cross(v,w);
return p+v*t;
} bool onsegment(point p,point a1,point a2){
return dcmp(cross(a1-p,a2-p))==&&dcmp(dot(a1-p,a2-p))<;
} polygon cutploygon(polygon poly,line ln){
polygon newploy;
int m=;
int n = poly.Size;
point a = ln.fir,b = ln.sec;
for(int i=;i<n;i++){
point c = poly.p[i];
point d = poly.p[(i+)%n];
double cc = cross(b-a,c-a);
double dd = cross(b-a,d-a);
if(cc>=)
newploy.p[m++] = c;
if(cc*dd<)
newploy.p[m++] = getLineIntersection(a,b-a,c,d-c);
}
newploy.Size = m;
return newploy;
} int main()
{
int n;
while(cin>>n&&n){
for(int i=;i<n;i++)
cin>>p[i].x>>p[i].y;
polygon poly;
poly.Size = ;
poly.p[].x = -maxn;
poly.p[].y = -maxn;
poly.p[].x = maxn;
poly.p[].y = -maxn;
poly.p[].x = maxn;
poly.p[].y = maxn;
poly.p[].x = -maxn;
poly.p[].y = maxn;
bool flag = true;
for(int i=;i<n;i++){
line ln;
ln.fir = p[i%n];
ln.sec = p[(i+)%n];
poly = cutploygon(poly,ln);
if(poly.Size==){
flag = false;
break;
}
}
if(!flag)
cout<<""<<endl;
else
cout<<""<<endl;
}
return ;
} /*************************************/
poj 点序顺时针
/*************************************/
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps = 1e-;
const double maxn = 0x7f7f7f7f;
int dcmp(double x){
if(fabs(x)<eps)
return ;
else
return x<?-:;
}
struct point {
double x,y;
point (double x=,double y =):x(x),y(y){}
};
point p[];
typedef point Vector; struct polygon{
point p[];
int Size;
}; struct line{
point fir,sec;
line(point a = point(),point b = point()){
fir = a;
sec = b;
}
}; Vector operator -(point a,point b){
return Vector(a.x-b.x,a.y-b.y);
} Vector operator *(Vector a,double p){
return Vector (a.x*p,a.y*p);
}
Vector operator + (Vector a,Vector b){
return Vector (a.x+b.x,a.y+b.y);
} double cross(Vector a,Vector b){
return a.x*b.y-a.y*b.x;
} double dot(Vector a,Vector b){
return a.x*b.x+a.y*b.y;
} point getLineIntersection(point p,Vector v,point q,Vector w){
Vector u = p-q;
double t = cross(w,u)/cross(v,w);
return p+v*t;
} bool onsegment(point p,point a1,point a2){
return dcmp(cross(a1-p,a2-p))==&&dcmp(dot(a1-p,a2-p))<;
} polygon cutploygon(polygon poly,line ln){
polygon newploy;
int m=;
int n = poly.Size;
point a = ln.fir,b = ln.sec;
for(int i=;i<n;i++){
point c = poly.p[i];
point d = poly.p[(i+)%n];
double cc = cross(b-a,c-a);
double dd = cross(b-a,d-a);
if(cc>=)
newploy.p[m++] = c;
if(cc*dd<)
newploy.p[m++] = getLineIntersection(a,b-a,c,d-c);
}
newploy.Size = m;
return newploy;
} int main()
{
int n;
int cnt =;
while(cin>>n&&n){
for(int i=;i<n;i++)
cin>>p[i].x>>p[i].y;
polygon poly;
poly.Size = ;
poly.p[].x = -maxn;
poly.p[].y = -maxn;
poly.p[].x = maxn;
poly.p[].y = -maxn;
poly.p[].x = maxn;
poly.p[].y = maxn;
poly.p[].x = -maxn;
poly.p[].y = maxn;
bool flag = true;
for(int i=;i<=n;i++){
line ln;
ln.fir = p[i%n];
ln.sec = p[i-];
poly = cutploygon(poly,ln);
if(poly.Size==){
flag = false;
break;
}
}
//cout<<poly.Size<<endl;
cout<<"Floor #"<<cnt++<<endl;
if(!flag)
cout<<"Surveillance is impossible."<<endl;
else
cout<<"Surveillance is possible."<<endl;
cout<<endl;
}
return ;
} /**********************************
poj 1279 点序顺时针
**********************************/
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std;
const double eps = 1e-;
const double maxn = 0x7f7f7f7f;
int dcmp(double x){
if(fabs(x)<eps)
return ;
else
return x<?-:;
}
struct point {
double x,y;
point (double x=,double y =):x(x),y(y){}
};
point p[];
typedef point Vector; struct polygon{
point p[];
int Size;
}; struct line{
point fir,sec;
line(point a = point(),point b = point()){
fir = a;
sec = b;
}
}; Vector operator -(point a,point b){
return Vector(a.x-b.x,a.y-b.y);
} Vector operator *(Vector a,double p){
return Vector (a.x*p,a.y*p);
}
Vector operator + (Vector a,Vector b){
return Vector (a.x+b.x,a.y+b.y);
} double cross(Vector a,Vector b){
return a.x*b.y-a.y*b.x;
} double dot(Vector a,Vector b){
return a.x*b.x+a.y*b.y;
} point getLineIntersection(point p,Vector v,point q,Vector w){
Vector u = p-q;
double t = cross(w,u)/cross(v,w);
return p+v*t;
} bool onsegment(point p,point a1,point a2){
return dcmp(cross(a1-p,a2-p))==&&dcmp(dot(a1-p,a2-p))<;
} polygon cutploygon(polygon poly,line ln){
polygon newploy;
int m=;
int n = poly.Size;
point a = ln.fir,b = ln.sec;
for(int i=;i<n;i++){
point c = poly.p[i];
point d = poly.p[(i+)%n];
double cc = cross(b-a,c-a);
double dd = cross(b-a,d-a);
if(cc>=)
newploy.p[m++] = c;
if(cc*dd<)
newploy.p[m++] = getLineIntersection(a,b-a,c,d-c);
}
newploy.Size = m;
return newploy;
} double polyArea(point *p,int n){
double area =;
for(int i=;i<n-;i++){
area += cross(p[i]-p[],p[i+]-p[]);
}
return area/;
} int main()
{
int t;
cin>>t;
int n;
while(t--){
cin>>n;
for(int i=;i<n;i++)
cin>>p[i].x>>p[i].y;
polygon poly;
poly.Size = ;
poly.p[].x = -maxn;
poly.p[].y = -maxn;
poly.p[].x = maxn;
poly.p[].y = -maxn;
poly.p[].x = maxn;
poly.p[].y = maxn;
poly.p[].x = -maxn;
poly.p[].y = maxn;
bool flag = true;
for(int i=;i<=n;i++){
line ln;
ln.fir = p[i%n];
ln.sec = p[i-];
poly = cutploygon(poly,ln);
if(poly.Size==){
flag = false;
break;
}
}
double res;
if(!flag)
res =;
else{
res = polyArea(poly.p,poly.Size);
}
printf("%.2lf\n",res);
}
return ;
}
上一篇:开发检测MySQL主从同步插件


下一篇:c++数组指针bug