TFIELD – SPOJ

Đề bài:


Thuật toán:


    Ngay từ đầu đề bài đã đề cập đến phần hình học.

    – Ta cần biết vị trí của các khoang theo đúng thứ tự (ví dụ từ trong ra ngoài). Ta có nhận xét là đa giác của khoang trong luôn có diện tích nhỏ hơn đa giác của khoang ngoài. Vì thế, ta chỉ cần sắp xếp các đa giác theo diện tích của chúng. Công thức tính diện tích 1 đa giác bất kì:

    S=1/2 ∑(x[i]-x[i+1])*(y[i]+y[i+1]) (với i=[1..n], quy ước điểm thứ n+1 chính là điểm 1).

    – Sau khi sắp xếp, ta có thể tính được diện tích từng khoang (diện tích khoang thứ i=s[i]-s[i-1]).

    – Bài toán đặt ra bây giờ là tìm đoạn khoang có diện tích lớn nhất nằm giữa 2 đa giác. Ta dùng đếm phân phối để giải quyết. Đầu tiên, ta cố định điểm trái của vùng cần xét O(m). Từ điểm này, tìm điểm phải nhất có số khoang cần đổi màu không quá k (nói cách khác là c-st<=k, với c là tổng số khoang của vùng, st là số khoang cùng màu của vùng) O(m). – Kết quả bài toán là kết quả tối ưu trong các giá trị đã xét. Độ phức tạp ~O(m^2).

Code:


uses    math;
const   fi='';
        fo='';
        maxn=1000+3;
type
        dinh    =record
                        x,y:longint;
                        end;
        arr1    =array[1..maxn] of dinh;
var     a       :array[1..maxn,1..maxn] of dinh;
        s       :array[1..maxn] of int64;
        i,j,n,m,k       :longint;
        c       :array[1..maxn] of longint;
        sodinh  :array[1..maxn] of longint;
        khoang  :array[1..maxn] of int64;
        res     :int64;
        dem     :array[1..maxn] of longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        read(m,k);
        for i:=1 to m do
                begin
                        read(sodinh[i],c[i]);
                        for j:=1 to sodinh[i] do read(a[i,j].x,a[i,j].y);
                end;
        close(input);
end;
procedure swap(var x,y:int64);
var     tg      :int64;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure swap2(var x,y:longint);
var     tg      :longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure qs(l,r:longint);
var     x:extended;
        i,j:longint;
begin
        i:=l;j:=r;
        x:=s[(l+r) div 2];
        repeat
                while x<s[i] do inc(i);
                while x>s[j] do dec(j);
                if i<=j then
                        begin
                                swap(s[i],s[j]);
                                swap2(c[i],c[j]);
                                inc(i);dec(j);
                        end;
        until i>j;
        if i<r then qs(i,r);
        if j>l then qs(l,j);
end;
function dientich(p:arr1;n:longint):int64;
var     i       :longint;
begin
        dientich := 0;
        p[n+1] := p[1];
        for i:=1 to n do
                dientich:= dientich + int64( (p[i+1].x-p[i].x) )*(p[i+1].y+p[i].y);
        dientich:= abs(dientich){/2};
end;
procedure tinhs;
var     i:longint;
begin
        for i:=1 to m do
                s[i]:=dientich(a[i],sodinh[i]);
end;
procedure chuanbi;
begin
        sodinh[n+1]:=4;
        a[n+1,1].x:=1;
        a[n+1,1].y:=1;
        a[n+1,2].x:=1;
        a[n+1,2].y:=1;
        a[n+1,3].x:=1;
        a[n+1,3].y:=1;
        a[n+1,4].x:=1;
        a[n+1,4].y:=1;
end;
procedure process;
var     maxc,sokhoang        :longint;
        dientich        :int64;
begin
        tinhs;
        s[m+1]:=0;
        qs(1,m+1);
        for i:=1 to m do
                khoang[i]:=s[i]-s[i+1];
        for i:=1 to m do
                begin
                        fillchar(dem,sizeof(dem),0); dientich := 0; maxc :=1; sokhoang :=1;
                        inc(dem[c[i]]);
                        dientich := dientich + khoang[i]; if dientich>res then res := dientich;
                        for j := i+1 to m do
                        begin
                                inc(dem[c[j]]); inc(sokhoang);
                                maxc := max(maxc,dem[c[j]]);
                                if sokhoang-maxc<=k then
                                        begin
                                                dientich := dientich + khoang[j];
                                                if dientich>res then res := dientich;
                                        end else break;
                        end;
                end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        write(res{:0:1} div 2);
        if odd(res) then
                write('.5') else write('.0');
        close(output);
end;
begin
        enter;
        process;
        print;
end.
#include<bits/stdc++.h>
#define db double
#define fs first
#define sc second
#define maxn 1005
#define ll long long
using namespace std;
int n,k,d[maxn],sum[maxn];
struct data
{
            ll s;
            int c;
};
data a[maxn];
ll res;
typedef pair<int,int> II;
II c[maxn][maxn];
void tinh(int k)
{
            d[k]++;
            c[k][d[k]].fs=c[k][1].fs;
            c[k][d[k]].sc=c[k][1].sc;
            for (int i=2; i<=d[k]; ++i)
            {
                        a[k].s+=((ll)(c[k][i].fs-c[k][i-1].fs)*(c[k][i].sc+c[k][i-1].sc));
            }
            if (a[k].s<0) a[k].s=-a[k].s;
}
bool cmp(const data &a,const data &b)
{
            return a.s<b.s;
}
int main()
{
            //freopen("TFIELD.inp","r",stdin);
            ios::sync_with_stdio(0);
            cin.tie(0);
            cout.tie(0);
            cin>>n>>k;
            for (int i=1; i<=n; ++i)
            {
                        cin>>d[i]>>a[i].c;
                        for (int j=1; j<=d[i]; ++j)
                                    cin>>c[i][j].fs>>c[i][j].sc;
            }
            for (int i=1; i<=n; ++i) tinh(i);
            sort(a+1,a+n+1,cmp);
            sum[n+1]=1000000000;
            for (int i=1; i<=n; ++i)
            {
                        sum[0]=0;
                        for (int j=1; j<=n; ++j)
                                    if (a[j].c!=i) sum[j]=sum[j-1]+1;
                                    else sum[j]=sum[j-1];
                        int r=1;
                        for (int l=1;l<=n;++l)
                        {
                                    while(sum[r+1]-sum[l-1]<=k)
                                                ++r;
                                    res=max(res,a[r].s-a[l-1].s);
                        }
            }
            cout<<res/2;
            if (res%2) cout<<".5";
            else cout<<".0";
            return 0;
}
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*